【题意】：和poj 3204一样，问在一个网络里面，增加哪条边的容量会使网络总流量增加？不同的是poj是输出有多少条这样的边，而zoj是输出是哪些边。
【题解】：原谅我的懒惰，请参照我poj 3204的题解，直接上代码算了，和那个基本一样。提醒一下，注意PE，不能有最后的空格。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "vector"
5 #include "queue"
6 using namespace std;
7 #define maxn 105
8 #define maxm 5005
9 const int INF = 999999999;
10 int n, n1, n2, m, s, t;
11 int ans[maxm], tot1, cnt[maxn], eh[maxn], pre[maxn], cur[maxn], dist[maxn], color[maxn], tot, low[maxn];
12 vector<int> vecs[maxn], vect[maxn];
13 queue<int> que;
14
15 struct Edge {
16 int u, v, cap, flow, next;
17 }et[maxm];
18
19 void init() {
20 tot = tot1 = 0;
21 memset(eh, -1, sizeof(eh));
22 memset(color, 0, sizeof(color));
23 }
24
25 void add(int u, int v, int cap, int flow) {
26 Edge E = {u, v, cap, flow, eh[u]};
27 et[tot] = E;
28 eh[u] = tot++;
29 }
30
31 void addedge(int u, int v, int cap) {
32 add(u, v, cap, 0), add(v, u, 0, 0);
33 }
34
35 int isap(int s, int t, int n) {
36 int u, v, now, flow = 0;
37 memset(dist, 0, sizeof(dist));
38 memset(low, 0, sizeof(low));
39 memset(cnt, 0, sizeof(cnt));
40 for(u = 0; u <= n; u++) cur[u] = eh[u];
41 low[s] = INF, cnt[0] = n;
42 u = s;
43 while(dist[s] < n) {
44 for(now = cur[u]; now != -1; now = et[now].next)
45 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1) break;
46 if(now != -1) {
47 cur[u] = pre[v] = now;
48 low[v] = min(low[u], et[now].cap - et[now].flow);
49 u = v;
50 if(u == t) {
51 for(; u != s; u = et[pre[u]].u) {
52 et[pre[u]].flow += low[t];
53 et[pre[u]^1].flow -= low[t];
54 }
55 low[s] = INF, flow += low[t];
56 }
57 } else {
58 if(--cnt[dist[u]] == 0) break;
59 dist[u] = n;
60 cur[u] = eh[u];
61 for(now = eh[u]; now != -1; now = et[now].next)
62 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
63 dist[u] = dist[et[now].v] + 1;
64 cnt[dist[u]]++;
65 if(u != s) u = et[pre[u]].u;
66 }
67 }
68 return flow;
69 }
70
71 void dfs1(int u) {
72 color[u] = 1;
73 int size = vecs[u].size();
74 for(int i = 0; i < size; i++) {
75 int v = vecs[u][i];
76 if(!color[v]) dfs1(v);
77 }
78 }
79
80 void dfs2(int u) {
81 color[u] = 2;
82 int size = vect[u].size();
83 for(int i = 0; i < size; i++) {
84 int v = vect[u][i];
85 if(!color[v]) dfs2(v);
86 }
87 }
88
89 int main() {
90 int u, v, cap, i;
91 while(scanf("%d%d%d", &n1, &n2, &m) != EOF) {
92 if(n1 == 0) break;
93 init();
94 s = n1 + n2 + 1, t = 0, n = s + 1;
95 for(i = 0; i <= n; i++) vecs[i].clear(), vect[i].clear();
96 for(i = 0; i < m; i++) {
97 scanf("%d%d%d", &u, &v, &cap);
98 addedge(u, v, cap);
99 }
100 for(i = 1; i <= n1; i++) addedge(s, i, INF);
101 isap(s, t, n);
102 for(i = 0; i < tot; i += 2) {
103 if(et[i].cap - et[i].flow) {
104 u = et[i].u, v = et[i].v;
105 vecs[u].push_back(v);
106 vect[v].push_back(u);
107 } else que.push(i);
108 }
109 dfs1(s), dfs2(t);
110 while(!que.empty()) {
111 i = que.front();
112 que.pop();
113 u = et[i].u, v = et[i].v;
114 if(color[u] == 1 && color[v] == 2)
115 ans[tot1++] = i / 2 + 1;
116 }
117 if(tot1) {
118 for(i = 0; i < tot1 - 1; i++)
119 printf("%d ", ans[i]);
120 printf("%d\n", ans[tot1 - 1]);
121 } else printf("\n");
122 }
123 return 0;
124 }