题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
本题是最大流算法的简单应用。
最大网络流的基本思想很简单——从某个初始流开始，反复的增加流的流量知道不能再改进为止。最后得到的流将是一个最大流。
定理 设 P 是网络 G 中从起点到终点满足一下条件的一条路径：
(a) 对P中的每条正向边(i,j)， Fij < Cij
(b)对P中的每条反向边(i,j)， Fij > 0
设 D是由P中所有正向边(i,j)对应的数和P中所有反向边(i,j)对应的数组成。
Δ =min D
Fij 如果(i,j)不在P中
F*ij={ Fij+ Δ 如果(i,j)在P中且是正向的
Fij-Δ 如果(i,j)在P中且不是正向的
根据上述定理，如果找不到路径满足上述定理，那么得到的流便是最大的。我们可以构造一个算法：
1.从一个流开始；
2.寻找一个满足上述定理的路径，如果这样的路径不存在，则停止，流是最大的；
3.将流过这条路径的流量增加△，转到第2行。
Ford-Fulkerson方法是按照上述定理构造，解决最大流问题的有效方法，一般采用深搜策略；而Edmonds-Karp算法是Ford-Fulkerson方法的广搜的实现；相对而言，后者的效率稍微高一些。
下面是POJ 1273的代码，采用的是Edmonds-Karp算法。
1
#include <cstdio>
2#include <queue>
3const int INF=0x0fffffff;
4const int SIZE=202;
5
6int bfs(int (*mat)[SIZE],int start,int end,int* path)
7
{
8
int flow[SIZE];//存储一次BFS遍历之后流的可改进量；
9 std::queue<int> q;
10 int i;
11
12 for(i=0;i<SIZE;++i)
13 path[i]=-1;
14 path[start]=0,flow[start]=INF;
15
16 q.push(start);
17 while(!q.empty())
18
{
19 int top=q.front();
20 q.pop();
21 if(top==end) break;
22 for(i=1;i<=end;++i)
23 {
24 if(i != start && path[i]==-1 && mat[top][i])
25 {
26 flow[i]=flow[top]<mat[top][i] ? flow[top] : mat[top][i];
27 q.push(i);
28 path[i]=top;
29
}
30 }
31 }
32 if(path[end]==-1) return -1;
33 return flow[end];
34
35
36
}
37int Edmonds_Karp(int (*mat)[SIZE],int start,int end)
38{
39 int maxflow=0,step,cur,pre;
40 int path[SIZE]; /**/////存储当前已访问过的节点的增广路径；
41 while((step=bfs(mat,start,end,path)) != -1)//找不到增广路径时退出
42 {
43 maxflow += step;
44 cur=end;
45 while(cur != start)
46 {
47 pre=path[cur];
48 mat[pre][cur] -= step; //更新正向边的实际容量
49 mat[cur][pre] += step; //添加反向边
50 cur=pre;
51 }
52 }
53 return maxflow;
54}
55
56int main()
57{
58 int mat[SIZE][SIZE];
59 int vecNum,edgeNum;
60 int i;
61 int a,b,c;
62
63 while(scanf("%d%d",&edgeNum,&vecNum)!=EOF)
64 {
65 memset(mat,0,sizeof(mat));
66 for(i=0;i<edgeNum;++i)
67 {
68 scanf("%d%d%d",&a,&b,&c);
69 mat[a][b]+=c;
70 }
71
72 int re=Edmonds_Karp(mat,1,vecNum);
73 printf("%d\n",re);
74
75 }
76 return 0;
77}
78