【题意】：在一个网络里面，问增大哪条边的容量可以使整个网络的流量增大，求有多少条这样的边？
【题解】：显然我们要找的边是在最小割集的边，但在最小割集的边不一定都满足条件。例如，s->1->2->t，假如每条边的容量都是5，显然任意一条边都是一个最小割集，但增加哪一条边都不会使网络的流量增加。因此我们找的割边还需要满足一个条件：假如有割边<u,v>，源点s必须可以从残量网络到达u，并且v可以从残量网络到达汇点t。那么增加<u,v>的容量必定有新流量可以沿s->u->v->t增加。具体做法：先求一次最大流，然后从s遍历残量网络，可到达的顶点染色为1；从t沿着反残量网络遍历，可到达的顶点染色为2。然后枚举每条边，如果两端点有色且染色不同，那么该边就是我们要找的关键割边了。其实，枚举边的时候只需枚举满流的边，因为满流的边才能是最小割集的边。
【代码】：
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