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!

 #include <iostream>

 #include <cstring>

 #include <queue>

 #include <stdio.h>

 #define msize 210

 #define INF 1000000000

 using namespace std;

 int origin[msize][msize]={};

 int r[msize][msize]={}; //残留网络，初始为原图

 bool visited[msize];

 int pre[msize];

 int m,nVertex; //n条边，m个顶点

 bool bfs(int s,int t) //寻找一条从s到t的增广路，若找到，返回true

 {

     int p;

     queue<int> Q;

     memset(pre,-,sizeof(pre));

     memset(visited,false,sizeof(visited));

     pre[s]=s;

     visited[s]=true;

     Q.push(s);

     while (!Q.empty())

     {

         p=Q.front(),Q.pop();

         for (int i=; i<=nVertex; i++)

         {

             if (r[p][i]>&&!visited[i])

             {

                 pre[i]=p;

                 visited[i]=true;

                 if (i==t) return true;

                 Q.push(i);

             }

         }

     }

     return false;

 }

 int maxFlow(int s,int t)

 {

     int flow=,d;

     while (bfs(s,t))

     {

         d=INF;

         for (int i=t; i!=s; i=pre[i]) d=min(d,r[pre[i]][i]);

         for (int i=t; i!=s; i=pre[i]) r[pre[i]][i] -= d, r[i][pre[i]] += d;

         flow += d;

     }

     return flow;

 }

 int main()

 {

     freopen("telecow.in","r",stdin);

     freopen("telecow.out","w",stdout);

     int s,e,c;

     cin>>nVertex>>m>>s>>e;

     nVertex*=;

     for(int i=;i<m;i++)

     {

         int a,b;

         scanf("%d%d",&a,&b);

         r[a*-][a*]=;

         r[b*-][b*]=;

         r[a*][b*-]=INF;

         r[b*][a*-]=INF;

     }

     memcpy(origin,r,sizeof r);

     int maxflow=maxFlow(s*,e*-);

     int sum=maxflow;

     memcpy(r,origin,sizeof r);

     printf("%d\n",maxflow);

     bool first=true;

     int cnt=;

     for(int i=;i<=nVertex/;i++) // 模拟删掉第i个点

     {

         if(i==s || i==e)

             continue;

         if(cnt==sum)

         {

             break;

         }

         memcpy(origin,r,sizeof r);

         r[i*-][i*]=;

         if(maxFlow(s*,e*-)+==maxflow)

         {

             maxflow--;

             cnt++;

             if(first)

             {

                 first=false;

             }

             else

             {

                 printf(" ");

             }

             printf("%d",i);

             memcpy(r,origin,sizeof r);

             r[i*-][i*]=;

         }

         else

         {

             memcpy(r,origin,sizeof r);

         }

     }

     cout<<endl;

     return ;

 }

巴特西

USACO5.4-TeleCowmunication

最新文章

热门文章