转载

[POJ1273]Drainage Ditches 网络流(最大流)

题目链接：http://poj.org/problem?id=1273

网络流裸题，注意有重边。重边的处理方法很简单，就是将对应的c叠加到对应边上。注意初始化为0。

我用的是最朴素的FF方法，即找增广路。之前用dfs找增广路WA了，应该是碰到了随机找一条增光路这种方法碰到了killer case。给出WA代码（初学用喜闻乐见链式前向星建图，比较繁琐。不过好在最终还是WA掉了）。

1 #include <algorithm>  2 #include <iostream>  3 #include <iomanip>  4 #include <cstring>  5 #include <climits>  6 #include <complex>  7 #include <fstream>  8 #include <cassert>  9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19  20 using namespace std; 21  22 typedef struct Edge { 23     int v; 24     int c; 25     int next; 26     Edge() { next = -1; } 27 }Edge; 28  29 const int maxn = 222; 30 int n, m, s, t; 31 int head[maxn]; 32 int vis[maxn]; 33 int cnt = 0; 34 Edge edge[maxn<<1]; 35  36 void init() { 37     memset(head, -1, sizeof(head)); 38     memset(vis, 0, sizeof(vis)); 39     cnt = 0; 40 } 41  42 void adde(int u, int v, int c) { 43     edge[cnt].v = v; edge[cnt].next = head[u]; 44     edge[cnt].c = c; head[u] = cnt++; 45     edge[cnt].v = v; edge[cnt].next = head[u]; 46     edge[cnt].c = 0; head[v] = cnt++; 47 } 48  49 int dfs(int v, int f) { 50     if(v == t) return f; 51     vis[v] = 1; 52     for(int i = head[v]; ~i; i = edge[i].next) { 53         if(!vis[edge[i].v] && edge[i].c > 0) { 54             int d = dfs(edge[i].v, min(f, edge[i].c)); 55             if(d > 0) { 56                 edge[i].c -= d; 57                 edge[i+1].c += d; 58                 return d; 59             } 60         } 61     } 62     return 0; 63 } 64  65 int max_flow() { 66     int flow = 0; 67     while(1) { 68         memset(vis, 0, sizeof(vis)); 69         int tf = dfs(s, 2147483647); 70         if(tf == 0) return flow; 71         flow += tf; 72     } 73     return flow; 74 } 75  76 int main() { 77     // freopen("in", "r", stdin); 78     int u, v, c; 79     while(~scanf("%d %d", &m, &n)) { 80         init(); 81         for(int i = 0; i < m; i++) { 82             scanf("%d %d %d", &u, &v, &c); 83             adde(u, v, c); 84         } 85         s = 1; 86         t = n; 87         printf("%d/n", max_flow()); 88     } 89     return 0; 90 }

随后索性全部删掉一切从简，改用最简单的邻接矩阵。利用BFS，第一次接触到汇点的那条路径一定是最短的（因为BFS是层进的）。找到了这条路并且记录下来即可。

接着，从源向外发出一个流（一定要足够大），按照之前BFS到的最短增广路流向汇点，根据短板效应找到流量，更新到最大流量上之后再更新残余网络（直接在原网络上更新即可）。下图可以比较清晰地说明这一点：

[POJ1273]Drainage Ditches 网络流(最大流)

简要证明：

我们从右图化简它的过程以及路径得到了右图。假设图中的源点可由b流经a到达汇点，而且假设b->a在当前所找到的增广路上，表示为G[b][a]。再假设该路上的流量为k，容量为n，那么当前b->a上的流量应被修改为k，且该路径在残余网络上残余的容量是n-k。而残余网络上，该路径表示为G[a][b]。如左图所示，对这两条路进行了一次合并，那么规定原图上初始流向为正方向，那么当前网络和残余网络上该路上的流量应当是n+(-(n-k))=n-n+k=k。因此只需要对两部分更新流量k就好了。在代码中，b相当于a的前驱点，也就是pre[a]。那么我们更新残余网络上对应的路的时候（也就是更新G[a][pre[a]]），相当于+k，而更新原图(G[pre[a]][a])的时候，相当于-k。

代码如下：

1 #include <algorithm>  2 #include <iostream>  3 #include <iomanip>  4 #include <cstring>  5 #include <climits>  6 #include <complex>  7 #include <fstream>  8 #include <cassert>  9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19  20 using namespace std; 21  22 const int inf = 0x7fffff; 23 const int maxn = 222; 24 int G[maxn][maxn]; 25 int pre[maxn]; 26 int vis[maxn]; 27 int m, n, s, t; 28  29 void init() { 30     memset(G, 0, sizeof(G)); 31     memset(pre, 0, sizeof(pre)); 32     memset(vis, 0, sizeof(vis)); 33 } 34  35 bool bfs() { 36     memset(vis, 0, sizeof(vis)); 37     memset(pre, 0, sizeof(pre)); 38     queue<int> q; 39     q.push(s); 40     vis[s] = 1; 41     while(!q.empty()) { 42         int v = q.front(); q.pop(); 43         for(int i = 1; i <= n; i++) { 44             if(G[v][i] > 0 && !vis[i]) { 45                 q.push(i); 46                 vis[i] = 1; 47                 pre[i] = v; 48                 if(i == n) { 49                     return 1; 50                 } 51             } 52         } 53     } 54     return 0; 55 } 56  57 int max_flow() { 58     int flow = 0; 59     while(1) { 60         if(!bfs()) return flow; 61         int v = n; 62         int k = inf; 63         while(pre[v]) { 64             k = min(k, G[pre[v]][v]); 65             v = pre[v]; 66         } 67         v = n; 68         flow += k; 69         while(pre[v]) { 70             G[v][pre[v]] += k; 71             G[pre[v]][v] -= k; 72             v = pre[v]; 73         } 74     } 75     return flow; 76 } 77  78 int main() { 79     // freopen("in", "r", stdin); 80     int u, v, c; 81     while(~scanf("%d %d", &m, &n)) { 82         init(); 83         for(int i = 0; i < m; i++) { 84             scanf("%d %d %d", &u, &v, &c); 85             G[u][v] += c; 86         } 87         s = 1; t = n; 88         printf("%d/n", max_flow()); 89     } 90 }

正文到此结束