首页 > 代码库 > USACO5.4-TeleCowmunication
USACO5.4-TeleCowmunication
题目大意:给出一个无向图,要求删除尽量少的点,使给定的2点间不再连通,并输出字典序最小的方案
题型:图论-网络流
此题难点在于建图,后面就是套网络流的模板.
将点看成边,例如第i个点可以看成一条有向边<i*2-1,i*2>,容量为1.
如果j点和i点邻接,那么新建2条容量为无穷大的有向边<i*2,j*2-1>,<j*2,i*2-1>.
然后应用最大流最小割定理,求最大流即为第一问答案.
接着枚举删除每一个点i(即删除有向边),看最大流是否减少1,如果是则该点在最小割中,然后真的把这一点删点.
枚举完每个点之后别忘了将残量网络还原.
至于为什么要这样建图, 一时间说不清楚......
Executing...
Test 1: TEST OK [0.008 secs, 3852 KB]
Test 2: TEST OK [0.014 secs, 3852 KB]
Test 3: TEST OK [0.005 secs, 3852 KB]
Test 4: TEST OK [0.022 secs, 3852 KB]
Test 5: TEST OK [0.011 secs, 3852 KB]
Test 6: TEST OK [0.019 secs, 3852 KB]
Test 7: TEST OK [0.019 secs, 3852 KB]
Test 8: TEST OK [0.014 secs, 3852 KB]
Test 9: TEST OK [0.032 secs, 3852 KB]
Test 10: TEST OK [0.046 secs, 3852 KB]
Test 11: TEST OK [0.068 secs, 3852 KB]
All tests OK.
Your program (‘telecow‘) produced all correct answers! This is your
submission #3 for this problem. Congratulations!
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 #include <stdio.h> 5 #define msize 210 6 #define INF 1000000000 7 using namespace std; 8 9 int origin[msize][msize]={0}; 10 int r[msize][msize]={0}; //残留网络，初始为原图 11 bool visited[msize]; 12 int pre[msize]; 13 int m,nVertex; //n条边，m个顶点 14 15 bool bfs(int s,int t) //寻找一条从s到t的增广路，若找到，返回true 16 { 17 int p; 18 queue<int> Q; 19 memset(pre,-1,sizeof(pre)); 20 memset(visited,false,sizeof(visited)); 21 22 pre[s]=s; 23 visited[s]=true; 24 Q.push(s); 25 26 while (!Q.empty()) 27 { 28 p=Q.front(),Q.pop(); 29 for (int i=1; i<=nVertex; i++) 30 { 31 if (r[p][i]>0&&!visited[i]) 32 { 33 pre[i]=p; 34 visited[i]=true; 35 if (i==t) return true; 36 Q.push(i); 37 } 38 } 39 } 40 41 return false; 42 } 43 44 int maxFlow(int s,int t) 45 { 46 int flow=0,d; 47 48 while (bfs(s,t)) 49 { 50 d=INF; 51 for (int i=t; i!=s; i=pre[i]) d=min(d,r[pre[i]][i]); 52 for (int i=t; i!=s; i=pre[i]) r[pre[i]][i] -= d, r[i][pre[i]] += d; 53 flow += d; 54 } 55 return flow; 56 } 57 58 int main() 59 { 60 freopen("telecow.in","r",stdin); 61 freopen("telecow.out","w",stdout); 62 int s,e,c; 63 64 cin>>nVertex>>m>>s>>e; 65 nVertex*=2; 66 for(int i=0;i<m;i++) 67 { 68 int a,b; 69 scanf("%d%d",&a,&b); 70 r[a*2-1][a*2]=1; 71 r[b*2-1][b*2]=1; 72 r[a*2][b*2-1]=INF; 73 r[b*2][a*2-1]=INF; 74 } 75 memcpy(origin,r,sizeof r); 76 int maxflow=maxFlow(s*2,e*2-1); 77 int sum=maxflow; 78 memcpy(r,origin,sizeof r); 79 printf("%d\n",maxflow); 80 81 bool first=true; 82 int cnt=0; 83 for(int i=1;i<=nVertex/2;i++) // 模拟删掉第i个点 84 { 85 if(i==s || i==e) 86 continue; 87 if(cnt==sum) 88 { 89 break; 90 } 91 memcpy(origin,r,sizeof r); 92 r[i*2-1][i*2]=0; 93 94 if(maxFlow(s*2,e*2-1)+1==maxflow) 95 { 96 maxflow--; 97 cnt++; 98 if(first) 99 {100 first=false;101 }102 else103 {104 printf(" ");105 }106 printf("%d",i);107 memcpy(r,origin,sizeof r);108 r[i*2-1][i*2]=0;109 }110 else111 {112 memcpy(r,origin,sizeof r);113 }114 }115 cout<<endl;116 return 0;117 }
USACO5.4-TeleCowmunication