在讨论问题之前先说一句，如果你这题WA了很久，请先看以下一句话，或许可以省下你翻遍全文的时间：
注意考虑重边。（是不是想大呼[Bi～]？传送门：http://poj.org/problem?id=1273）
嗯，接下来神犇们都走了，继续本文的主题。
一、网络和流(network-flows)
首先，什么是网络流呢？
根据中国人咬文嚼字的习惯，我们把它拆成“网络”和“流”两个概念。
网络：你可以认为这就是一个有向图，只不过有两个特殊的点：源点和汇点，分别只有出边和只有入边。
流：我们把网络上的每条边看做管子，它的边权看做管子单位时间内可以通过个流量，那么单位时间内从源点到汇点通过的流量就称作这个网络的一个流。在一个合法的流中，除了源点和汇点之外，每个节点入边的流量等于出边的流量，这就是流守恒(Flow Conservation)。
约定：c(u,v)表示u节点到v节点的容量，f(u,v)表示u节点到v节点的流量（注意：容量是网络的性质，是不可变的，而流量是一个动态的概念，不同的流下对于相同的边可能有不同的流量），G=(V,E,C)为整个网络。
性质：
1、容量限制：f(u,v) <= c(u,v)
2、反对称性：f(u,v) == -f(v,u)
3、流量守恒：∑f(u,v) == 0（v∈V）
二、剩余网络(residual capacity)和增广路(augment path)
剩余网络：指一个网络中已经有了一个流（可以为0），在原网络的容量基础上减去已经被“占用”的容量所得到的网络。
约定：r(u,v)表示u节点到v节点的剩余流量，即r(u,v) == c(u,v) - f(u,v)，由“流量限制”可得r(u,v) >= 0（注意：容量并不满足反对称性，所以规定不存在的边容量为0）。
增广路：如果在剩余网络中可以找到一条从源点到汇点的路径，满足所经过的边的剩余容量都严格大于0（注意这是剩余网络中的边），那么这条路径叫做剩余网络中的一条增广路。
三、题目解答
先贴代码：
1 /* 2 Problem: POJ1273 3 Author: DUSH 4 Algorithm: worknet-flows 5 */ 6 #include<ctime> 7 #include<cstdio> 8 #include<cstring> 9 #include<cstdlib> 10 #include<algorithm> 11 #include<queue> 12 13 #define file(f) freopen(f".in","r",stdin); freopen(f".out","w",stdout) 14 15 using namespace std; 16 const int maxn = 200 + 10; 17 const int data = 10000010; 18 19 int c[maxn][maxn],n,m,p[maxn];//n很小，就开二维数组吧，操作方便些 20 21 void init(){ 22 memset(c,0,sizeof(c));//记得清空数组 23 int u,v,w; 24 for(int i = 1;i <= n;++ i){ 25 scanf("%d%d%d",&u,&v,&w); 26 c[u][v] += w;//防止出现重边 27 } 28 } 29 30 bool spfa(int s,int t){ 31 bool in[maxn];//记录点是否在队列中 32 int dis[maxn];//记录所有点到源点的距离 33 memset(in,0,sizeof(in)); 34 memset(dis,-1,sizeof(dis)); 35 memset(p,-1,sizeof(p)); 36 dis[s] = 0; 37 queue<int> Q; 38 Q.push(s); 39 in[s] = 1; 40 while(!Q.empty()){ 41 int node = Q.front(); 42 if(node == t) break;//找到汇点就退出 43 Q.pop(); 44 in[node] = 0; 45 for(int i = 1;i <= m;++ i){ 46 if(i != node){ 47 if(c[node][i] > 0 && (dis[i] > dis[node] + 1 || dis[i] == -1)){ 48 dis[i] = dis[node] + 1;//找无权图的最短路 49 p[i] = node;//记录前驱 50 if(!in[i]){ 51 Q.push(i); 52 in[i] = 1; 53 } 54 }//注意这里找路径的时候剩余容量必须严格大于0 55 } 56 } 57 } 58 if(dis[t] == -1)//没找到增广路 59 return false; 60 else 61 return true; 62 } 63 64 void work(){ 65 int ans = 0,tmp; 66 while(spfa(1,m)){ 67 int u = m; 68 tmp = data; 69 while(p[u] != -1){ 70 tmp = min(tmp,c[p[u]][u]);//寻找路径上容量最小的边的容量 71 u = p[u]; 72 } 73 ans += tmp;//加入总答案 74 u = m; 75 while(p[u] != -1){ 76 c[p[u]][u] -= tmp; 77 c[u][p[u]] += tmp;//注意这个细节，增加反向边的容量，反例如下图 78 u = p[u]; 79 }//沿途修改剩余网络的容量 80 } 81 printf("%d\n",ans); 82 } 83 84 int main(){ 85 #ifndef ONLINE_JUDGE 86 file("1273"); 87 #endif 88 while(scanf("%d%d",&n,&m) != EOF){ 89 init(); 90 work(); 91 } 92 return 0; 93 }
说到为什么要增加反向边的容量，举个例子就知道了：
有这样一张图（1为源点，6为汇点）：
如果不加反向边，第一次增广的结果会是这样（红色为变化后的c值，橙色表示增广路）：
由上图得出最大流为2；
若加了反向边（绿色），第一次增广会是这样：
接下来进行第二次增广：
于是我们发现此时得到的最大流为3，如果手推也会得到这个答案。
这是为什么呢？
仔细观察之后会发现，这里其实出现了“分流”的情况，第一次增广时可以认为2节点处2单位的流量分别流向了3和5各一单位，而4节点处的流量则全部经过5节点流到汇点。然而在寻找最短路作为增广路时，我们并不能保证给出的边一定按照了1→2→3...的顺序，所以加上反向边相当于给了我们的程序“反悔”的机会，这时沿反向边的第二次增广就可以认为在5节点处把原本流经5节点的1单位的流量“挤”了上去走2→3→6的路径，也就是第二次增广出来的路径，反向边的容量就是可以“反悔”的剩余量，于是问题就圆满解决了。
