問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1273思路:
第一道最大流，Edmonds-Karp算法
參考了別人的代碼，其實自己也能寫出來，不過肯定沒有這么精致(*^__^*) 嘻嘻……
從別人的代碼里學到很多，例如：
一條路徑只需要pre[]數組進行保存即可，路徑的殘留容量也可以邊擴展(BFS)邊記錄，還有代碼居然就只需要一個殘留網絡的二維數組
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_M 201
5 #define INF 0x7FFFFFFF
6 #define Min(a,b) ((a)<(b) ? (a) : (b))
7 int n, m, source, sink;
8 int pre[MAX_M]; /* excellent for path recording */
9 int flow[MAX_M];
10 int residual[MAX_M][MAX_M]; /* only need this matrix */
11 int queue[MAX_M];
12
13 int
14 bfs() /* operation on the residual network */
15 {
16 int i, head, tail, cur;
17 head = -1;
18 tail = 0;
19 memset(pre, -1, sizeof(pre));
20 for(i=1; i<=m; i++)
21 flow[i] = INF;
22 queue[tail] = source;
23 pre[source] = 0;
24 while(head < tail) {
25 ++head;
26 cur = queue[head];
27 if(cur == sink)
28 return flow[sink];
29 for(i=1; i<=m; i++) {
30 if(pre[i]!=-1 || !residual[cur][i])
31 continue;
32 pre[i] = cur;
33 flow[i] = Min(flow[cur], residual[cur][i]);
34 ++tail;
35 queue[tail] = i;
36 }
37 }
38 return -1;
39 }
40
41 int
42 edmonds_karp()
43 {
44 int tmp, next, cur, rt = 0;
45 while(1) {
46 tmp = bfs();
47 if(tmp == -1) /* there's no argment path */
48 return rt;
49 rt += tmp;
50 cur = sink;
51 while(cur != source) {
52 next = cur;
53 cur = pre[cur];
54 residual[cur][next] -= tmp;
55 residual[next][cur] += tmp;
56 }
57 }
58 }
59
60 int
61 main(int argc, char **argv)
62 {
63 int i, f, t, c, ans;
64 while(scanf("%d %d", &n, &m) != EOF) {
65 memset(residual, 0, sizeof(residual));
66 for(i=1; i<=n; i++) {
67 scanf("%d %d %d", &f, &t, &c);
68 residual[f][t] += c; /* Attention: multiple lines */
69 }
70 source = 1;
71 sink = m;
72 ans = edmonds_karp();
73 printf("%d\n", ans);
74 }
75 }