【題意】：在一個(gè)網(wǎng)絡(luò)里面，問增大哪條邊的容量可以使整個(gè)網(wǎng)絡(luò)的流量增大，求有多少條這樣的邊？
【題解】：顯然我們要找的邊是在最小割集的邊，但在最小割集的邊不一定都滿足條件。例如，s->1->2->t，假如每條邊的容量都是5，顯然任意一條邊都是一個(gè)最小割集，但增加哪一條邊都不會(huì)使網(wǎng)絡(luò)的流量增加。因此我們找的割邊還需要滿足一個(gè)條件：假如有割邊<u,v>，源點(diǎn)s必須可以從殘量網(wǎng)絡(luò)到達(dá)u，并且v可以從殘量網(wǎng)絡(luò)到達(dá)匯點(diǎn)t。那么增加<u,v>的容量必定有新流量可以沿s->u->v->t增加。具體做法：先求一次最大流，然后從s遍歷殘量網(wǎng)絡(luò)，可到達(dá)的頂點(diǎn)染色為1；從t沿著反殘量網(wǎng)絡(luò)遍歷，可到達(dá)的頂點(diǎn)染色為2。然后枚舉每條邊，如果兩端點(diǎn)有色且染色不同，那么該邊就是我們要找的關(guān)鍵割邊了。其實(shí)，枚舉邊的時(shí)候只需枚舉滿流的邊，因?yàn)闈M流的邊才能是最小割集的邊。
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "vector"
4 #include "queue"
5 using namespace std;
6 #define maxn 505
7 #define maxm 50005
8 const int INF = 99999999;
9 int n, m, s, t;
10 int eh[maxn], pre[maxn], cur[maxn], dist[maxn], cnt[maxn], color[maxn], tot, low[maxn], ans;
11 vector<int> vecs[maxn], vect[maxn];
12 queue<int> que;
13 struct Edge {
14 int u, v, cap, flow, next;
15 }et[maxm];
16
17 void init() {
18 tot = ans = 0;
19 memset(eh, -1, sizeof(eh));
20 memset(color, 0, sizeof(color));
21 }
22
23 void add(int u, int v, int cap, int flow) {
24 Edge e = {u, v, cap, flow, eh[u]};
25 et[tot] = e;
26 eh[u] = tot++;
27 }
28
29 void addedge(int u, int v, int cap) {
30 add(u, v, cap, 0), add(v, u, 0, 0);
31 }
32
33 void isap(int s, int t, int n) {
34 int u, v, now, flow = 0;
35 memset(dist, 0, sizeof(dist));
36 memset(low, 0, sizeof(low));
37 memset(cnt, 0, sizeof(cnt));
38 for(u = 0; u <= n; u++) cur[u] = eh[u];
39 low[s] = INF, cnt[0] = n;
40 u = s;
41 while(dist[s] < n) {
42 for(now = cur[u]; now != -1; now = et[now].next) {
43 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1) break;
44 }
45 if(now != -1) {
46 cur[u] = pre[v] = now;
47 low[v] = min(low[u], et[now].cap - et[now].flow);
48 u = v;
49 if(u == t) {
50 for(; u != s; u = et[pre[u]].u) {
51 et[pre[u]].flow += low[t];
52 et[pre[u]^1].flow -= low[t];
53 }
54 low[s] = INF, flow += low[t];
55 }
56 } else {
57 if(--cnt[dist[u]] == 0) break;
58 dist[u] = n;
59 cur[u] = eh[u];
60 for(now = eh[u]; now != -1; now = et[now].next)
61 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
62 dist[u] = dist[et[now].v] + 1;
63 cnt[dist[u]]++;
64 if(u != s) u = et[pre[u]].u;
65 }
66 }
67 }
68
69 void dfs1(int u) {
70 color[u] = 1;
71 int size = vecs[u].size();
72 for(int i = 0; i < size; i++) {
73 int v = vecs[u][i];
74 if(!color[v]) dfs1(v);
75 }
76 }
77
78 void dfs2(int u) {
79 color[u] = 2;
80 int size = vect[u].size();
81 for(int i = 0; i < size; i++) {
82 int v = vect[u][i];
83 if(!color[v]) dfs2(v);
84 }
85 }
86
87 int main() {
88 int i, u, v, cap;
89 scanf("%d%d", &n, &m);
90 init();
91 for(i = 0; i < m; i++) {
92 scanf("%d%d%d", &u, &v, &cap);
93 if(cap) addedge(u, v, cap);
94 }
95 s = 0, t = n - 1;
96 isap(s, t, n);
97 for(i = 0; i < maxn; i++) vecs[i].clear(), vect[i].clear();
98 for(i = 0; i < tot; i += 2) {
99 if(et[i].cap - et[i].flow) {
100 u = et[i].u, v = et[i].v;
101 vecs[u].push_back(v);
102 vect[v].push_back(u);
103 } else que.push(i);
104 }
105 dfs1(s), dfs2(t);
106 while(!que.empty()) {
107 i = que.front();
108 que.pop();
109 u = et[i].u, v = et[i].v;
110 if(color[u] == 1 && color[v] == 2) ans++;
111 }
112 cout << ans << endl;
113 return 0;
114 }
115