【题意】:和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, -1sizeof(eh));
 22     memset(color, 0sizeof(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, 00);
 33 }
 34 
 35 int isap(int s, int t, int n) {
 36     int u, v, now, flow = 0;
 37     memset(dist, 0sizeof(dist));
 38     memset(low, 0sizeof(low));
 39     memset(cnt, 0sizeof(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] + 1break;
 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]] == 0break;
 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 == 0break;
 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 }