网络流-最小割边数和最小割边集求法

最小割边数：

求法一：

1.求出原网络的最大流.

2.把可能的关键割边（即满流的边）容量置为 1，其余边容量置为 0.

3.求出修改后网络的最大流.

此时的最大流即是最小割时最少的割边数。

总共求了 2 次最大流。

更好的求法二：

以下用 E 表示网络流中的边数.

1.建图时，把每条边的边权 w 置为 w * (E + 1) + 1.

2.求出修改后网络的最大流 flow_max.

此时原图的最大流为 flow_max / (E + 1) ，最少的割边数为 flow_max mod (E + 1). （E + 1 也可以换作一个大于等于它的任意数）

总共只求了 1 次最大流。

最小割边集：

在执行过 SAP 的残量网络上寻找满流的边（满流的边才可能是关键割边），即残量为 0 的边。从原图，原图，原图中删去这条边，即将正向边残量置为 0，并执行一次 SAP 得到最大流。如果原最大流与此时得到最大流的差正好为该边容量，且此时得到的最小割边数正好比原最小割边数少 1 （求法见上文），则将该边加入最小割边集。重复这个过程，直到残量网络上所有满流边被讨论完毕。

【USACO4.4.2】Pollutant Control追查坏牛奶就是一道考察这两个知识点的题目， NKOJ1852。

这道题困扰过我一段时间，代码如下：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const long long int MAXN = 55000;
 7 const long long int MAXM = 50005;
 8 const long long int INF = ~0ull >> 1;
 9 
10 long long int edge, n, m, s, t, ver;
11 long long int maxflow, mincut;
12 long long int v[MAXM], fst[MAXN], nxt[MAXM], tmpedge[MAXM];
13 long long int dis[MAXN], cnt[500000], c_ori[MAXM], c_tmp[MAXM];
14 
15 inline void insert(long long int x, long long int y, long long int z)
16 {
17     v[++edge] = y;
18     c_ori[edge] = z;
19     c_tmp[edge] = z;
20     nxt[edge] = fst[x];
21     fst[x] = edge;
22     //prlong long intf("[%d->%d  %d]  ", x, y, z);
23     return ;
24 }
25 
26 long long int SAP(long long int node, long long int flow)
27 {
28     if (node == t)
29         return flow;
30     long long int p, tmp, dlt = 0;
31     for (p = fst[node]; p; p = nxt[p]) {
32         if (c_tmp[p] <= 0 || dis[v[p]] + 1 != dis[node])
33             continue;
34         tmp = SAP(v[p], min(c_tmp[p], flow - dlt));
35         c_tmp[p] -= tmp;
36         c_tmp[p + 1] += tmp;
37         if ((dlt += tmp) == flow || dis[s] == ver)
38             return dlt;
39     }
40     if (!--cnt[dis[node]])
41         dis[s] = ver;
42     ++cnt[++dis[node]];
43     return dlt;
44 }
45 
46 int main()
47 {
48     long long int i, t1, t2, t3, tmpflow, cap, tot;
49     scanf("%I64d%I64d", &n, &m);
50     for (i = 1; i <= m; ++i) {
51         scanf("%I64d%I64d%I64d", &t1, &t2, &t3);
52         insert(t1, t2, t3 * (m + 1) + 1);
53         insert(t2, t1, 0);
54     }
55     s = 1;
56     t = n;
57     ver = n;
58     while (dis[s] < ver)
59         maxflow += SAP(s, INF);
60     mincut = maxflow % (m + 1);
61     maxflow /= (m + 1);
62     printf("%I64d %I64d
", maxflow, mincut);
63     t1 = m << 1;
64     tot = 0;
65     for (i = 1; i <= t1; i += 2)
66         if (!c_tmp[i])
67             tmpedge[++tot] = i;
68     for (i = 1; i <= tot && mincut; ++i) {
69         memcpy(c_tmp, c_ori, sizeof c_ori);
70         memset(dis, 0, sizeof dis);
71         memset(cnt, 0, sizeof cnt);
72         cap = c_tmp[tmpedge[i]] / (m + 1);
73         c_tmp[tmpedge[i]] = 0;
74         tmpflow = 0;
75         while (dis[s] < ver)
76             tmpflow += SAP(s, INF);
77         if (maxflow - tmpflow / (m + 1) == cap
78         && tmpflow % (m + 1) + 1 == mincut) {
79             printf("%I64d ", tmpedge[i] + 1 >> 1);
80             
81             --mincut;
82             maxflow -= cap;
83             c_ori[tmpedge[i]] = 0;
84         }
85     }
86     return 0;
87 }

View Code