poj1815Friendship(最小割求割边）

链接

题意为去掉多少个顶点使图不连通，求顶点连通度问题。拆点，构造图，对于<u,v>可以变成<u2,v1> <v2,u1>容量为无穷，<u1,u2>容量为1.那么求出来的最大流（即最小割）就为所需要删除的顶点个数，需要字典序输出，从小到大枚举顶点，如果不加入当前点，最小割变小了的话，说明这个点是肯定要删除的。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <algorithm>

 using namespace std;

 #define INF 0x3f3f3f

 const int N = ;

 #define M 160015

 struct node

 {

     int u,v,next;

     int w;

 } edge[M<<];

 int head[N],t,vis[N],pp[N],dis[N];

 int o[N];

 int st,en;

 int x[N][N],f[N];

 void init()

 {

     t=;

     memset(head,-,sizeof(head));

 }

 void add(int u,int v,int w)

 {

     edge[t].u = u;

     edge[t].v = v;

     edge[t].w = w;

     edge[t].next = head[u];

     head[u] = t++;

     edge[t].u = v;

     edge[t].v = u;

     edge[t].w = ;

     edge[t].next = head[v];

     head[v] = t++;

 }

 int bfs()

 {

     int i,u;

     int w;

     memset(dis,-,sizeof(dis));

     queue<int>q;

     q.push(st);

     dis[st] = ;

     while(!q.empty())

     {

         u = q.front();

         q.pop();

         for(i = head[u] ; i != - ; i = edge[i].next)

         {

             int v = edge[i].v;

             w = edge[i].w;

             if(dis[v]<&&w>)

             {

                 dis[v] = dis[u]+;

                 q.push(v);

             }

         }

     }

     if(dis[en]>) return ;

     return ;

 }

 int dfs(int u,int te)

 {

     int i;

     int s;

     if(u==en) return te;

     for(i = head[u] ; i != - ; i = edge[i].next)

     {

         int v = edge[i].v;

         int w = edge[i].w;

         if(w>&&dis[v]==dis[u]+&&(s=dfs(v,min(te,w))))

         {

             edge[i].w-=s;

             edge[i^].w+=s;

             return s;

         }

     }

     dis[u] = -;

     return ;

 }

 int dinic()

 {

     int flow = ;

     int res;

     while(bfs())

     {

         while(res = dfs(st,INF))

         flow+=res;

     }

     return flow;

 }

 int main()

 {

     int n,i,j;

     while(scanf("%d%d%d",&n,&st,&en)!=EOF)

     {

         init();

         // memset(x,0,sizeof(x));

         memset(f,,sizeof(f));

         st+=n;

         for(i = ; i <= n ; i++)

         {

             for(j = ; j <= n; j++)

             {

                 scanf("%d",&x[i][j]);

                 if(i==j)

                 {

                     add(i,i+n,);

                 }

                 else if(x[i][j])

                 {

                     add(i+n,j,INF);

                 }

             }

         }

         if(x[st-n][en])

         {

             puts("NO ANSWER!");

             continue;

         }

         int ans = dinic();

         int cnt = ;

         for(i = ; i <= n ; i++)

         {

             if(ans==) break;

             if(i==st-n||i==en) continue;

             f[i] = ;

             init();

             for(j = ; j <= n ; j++)

             {

                 if(f[j]) continue;

                 for(int e = ; e <= n ; e++)

                 {

                     if(f[e]) continue;

                     if(j==e)

                         add(j,j+n,);

                     else if(x[j][e])

                     {

                         add(j+n,e,INF);

                     }

                 }

             }

             int ts = dinic();

             if(ts<ans)

             {

                 cnt++;

                 ans = ts;

             }

             else f[i] = ;

         }

         cout<<cnt<<endl;

         for(j = ; j <= n; j++)

             if(f[j])

                 printf("%d ",j);

         printf("\n");

     }

     return ;

 }

巴特西

poj1815Friendship(最小割求割边）

最新文章

热门文章