poj 1815(最小割割集)

N个人，告诉一系列谁有谁的联系方式。问题：指定S,T两个人，问除这两个人以外，最少踢掉几个人，可以使得这两个人无法联系的上。给出字典序最小的一种方案。

拆点。因为题目要求的是剔除多少个点。我们要把他转换成剔除多少条边。所以要拆点。

枚举删除每一条边，其余边与原图一致，判断新图的最小割是否比原图减少。减少说明是割集的边。

  1 // File Name: 1815.cpp
  2 // Author: Missa
  3 // Created Time: 2013/4/18 星期四 19:31:30
  4 
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<algorithm>
  9 #include<cmath>
 10 #include<queue>
 11 #include<stack>
 12 #include<string>
 13 #include<vector>
 14 #include<cstdlib>
 15 #include<map>
 16 #include<set>
 17 using namespace std;
 18 #define CL(x,v) memset(x,v,sizeof(x));
 19 #define R(i,st,en) for(int i=st;i<en;++i)
 20 #define LL long long
 21 
 22 const int inf = 0x3f3f3f3f;
 23 const int maxn = 410;
 24 const int maxm = 160010;
 25 struct Edge
 26 {
 27     int v, c, next;//指向点,流量,下一个点
 28 }p[maxm << 1];
 29 int head[maxn], e;
 30 int d[maxn], cur[maxn];//层次记录，当前弧优化
 31 int n, m, st, en;
 32 void init()
 33 {
 34     e = 0;
 35     memset(head, -1, sizeof(head));
 36 }
 37 void addEdge(int u, int v, int c)
 38 {
 39     p[e].v = v; p[e].c = c; 
 40     p[e].next = head[u];head[u] = e++;
 41     p[e].v = u; p[e].c = 0; //无向图时逆边赋值流量cap，有向图时赋值0.
 42     p[e].next = head[v];head[v] = e++;
 43 }
 44 int bfs(int st, int en)
 45 {
 46     queue <int> q;
 47     memset(d, 0, sizeof(d));
 48     d[st] = 1;
 49     q.push(st);
 50     while (!q.empty())
 51     {
 52         int u = q.front(); q.pop();
 53         for (int i = head[u]; i != -1; i = p[i].next)
 54         {
 55             if (p[i].c > 0 && !d[p[i].v])
 56             {
 57                 d[p[i].v] = d[u] + 1;
 58                 q.push(p[i].v);
 59             }
 60         }
 61     }
 62     return d[en];
 63 }
 64 int dfs(int u, int a)//a表示流量
 65 {
 66     if (u == en || a == 0) return a;
 67     int f, flow = 0;
 68     for (int& i = cur[u]; i != -1; i = p[i].next)
 69     {
 70         if (d[u] + 1 == d[p[i].v] && (f = dfs(p[i].v,min(a,p[i].c))) > 0)
 71         {
 72             p[i].c -= f;
 73             p[i^1].c += f;
 74             flow += f;
 75             a -= f;
 76             if (!a) break;
 77         }
 78     }
 79     return flow;
 80 }
 81 int dinic(int st, int en)
 82 {
 83     int res = 0;
 84     while (bfs(st, en))
 85     {
 86         for (int i = 0; i <= n; ++i)
 87             cur[i] = head[i];
 88         res += dfs(st, inf);
 89     }
 90     return res;
 91 }
 92 int N;
 93 int g[210][210];
 94 bool del[210];
 95 void build()
 96 {
 97     init();
 98     for (int i = 1; i <= N; ++i)
 99     {
100         if (del[i]) continue;
101         for (int j = 1; j <= N; ++j)
102         {
103             if (del[j]) continue;
104             if (i == j)
105                 addEdge(i, j + N, 1);
106             else if (g[i][j])
107                 addEdge(i + N, j, inf);
108         }
109     }
110 }
111 
112 int main()
113 {
114     while(~scanf("%d%d%d",&N,&st,&en))
115     {
116         memset(del, 0, sizeof(del));
117         st += N;
118         n = N << 1;
119         for (int i = 1; i <= N; ++i)
120             for(int j = 1; j <= N; ++j)
121                 scanf("%d", &g[i][j]);
122         if(g[st - N][en])
123         {
124             printf("NO ANSWER!");
125             continue;
126         }
127         build();
128         int pre = dinic(st, en);
129         int ans = 0;
130         for (int i = 1; i <= N; ++i)
131         {
132             if (pre == 0) break;
133             if (i == st - N || i == en) continue;
134             del[i] = 1;
135             build();
136             int tmp = dinic(st, en);
137             if (tmp < pre){ans++; pre = tmp;}
138             else del[i] = 0;
139         }
140         printf("%d\n",ans);
141         for (int i = 1; i <= N; ++i)
142             if(del[i])
143                 printf("%d ",i);
144         printf("\n");
145     }
146     return 0;
147 }

poj 1815(最小割 割集)

poj 1815(最小割割集)