poj1815Friendship(最小割求割边）

链接

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

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #include <algorithm>
  6 using namespace std;
  7 #define INF 0x3f3f3f
  8 const int N = 415;
  9 #define M 160015
 10 struct node
 11 {
 12     int u,v,next;
 13     int w;
 14 } edge[M<<1];
 15 int head[N],t,vis[N],pp[N],dis[N];
 16 int o[N];
 17 int st,en;
 18 int x[N][N],f[N];
 19 void init()
 20 {
 21     t=0;
 22     memset(head,-1,sizeof(head));
 23 }
 24 void add(int u,int v,int w)
 25 {
 26     edge[t].u = u;
 27     edge[t].v = v;
 28     edge[t].w = w;
 29     edge[t].next = head[u];
 30     head[u] = t++;
 31     edge[t].u = v;
 32     edge[t].v = u;
 33     edge[t].w = 0;
 34     edge[t].next = head[v];
 35     head[v] = t++;
 36 }
 37 int bfs()
 38 {
 39     int i,u;
 40     int w;
 41     memset(dis,-1,sizeof(dis));
 42     queue<int>q;
 43     q.push(st);
 44     dis[st] = 0;
 45     while(!q.empty())
 46     {
 47         u = q.front();
 48         q.pop();
 49         for(i = head[u] ; i != -1 ; i = edge[i].next)
 50         {
 51             int v = edge[i].v;
 52             w = edge[i].w;
 53             if(dis[v]<0&&w>0)
 54             {
 55                 dis[v] = dis[u]+1;
 56                 q.push(v);
 57             }
 58         }
 59     }
 60     if(dis[en]>0) return 1;
 61     return 0;
 62 }
 63 int dfs(int u,int te)
 64 {
 65     int i;
 66     int s;
 67     if(u==en) return te;
 68     for(i = head[u] ; i != -1 ; i = edge[i].next)
 69     {
 70         int v = edge[i].v;
 71         int w = edge[i].w;
 72         if(w>0&&dis[v]==dis[u]+1&&(s=dfs(v,min(te,w))))
 73         {
 74             edge[i].w-=s;
 75             edge[i^1].w+=s;
 76             return s;
 77         }
 78     }
 79     dis[u] = -1;
 80     return 0;
 81 }
 82 int dinic()
 83 {
 84     int flow = 0;
 85     int res;
 86     while(bfs())
 87     {
 88         while(res = dfs(st,INF))
 89         flow+=res;
 90     }
 91     return flow;
 92 }
 93 int main()
 94 {
 95     int n,i,j;
 96     while(scanf("%d%d%d",&n,&st,&en)!=EOF)
 97     {
 98         init();
 99         // memset(x,0,sizeof(x));
100         memset(f,0,sizeof(f));
101         st+=n;
102         for(i = 1; i <= n ; i++)
103         {
104             for(j = 1; j <= n; j++)
105             {
106                 scanf("%d",&x[i][j]);
107                 if(i==j)
108                 {
109                     add(i,i+n,1);
110                 }
111                 else if(x[i][j])
112                 {
113                     add(i+n,j,INF);
114                 }
115             }
116         }
117         if(x[st-n][en])
118         {
119             puts("NO ANSWER!");
120             continue;
121         }
122         int ans = dinic();
123         int cnt = 0;
124         for(i = 1; i <= n ; i++)
125         {
126             if(ans==0) break;
127             if(i==st-n||i==en) continue;
128             f[i] = 1;
129             init();
130             for(j = 1; j <= n ; j++)
131             {
132                 if(f[j]) continue;
133                 for(int e = 1; e <= n ; e++)
134                 {
135                     if(f[e]) continue;
136                     if(j==e)
137                         add(j,j+n,1);
138                     else if(x[j][e])
139                     {
140                         add(j+n,e,INF);
141                     }
142                 }
143             }
144             int ts = dinic();
145             if(ts<ans)
146             {
147                 cnt++;
148                 ans = ts;
149             }
150             else f[i] = 0;
151         }
152         cout<<cnt<<endl;
153         for(j = 1; j <= n; j++)
154             if(f[j])
155                 printf("%d ",j);
156         printf("\n");
157     }
158     return 0;
159 }

View Code

秒客网

poj1815Friendship(最小割求割边）

相关文章