題目鏈接http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
本題是最大流算法的簡(jiǎn)單應(yīng)用。
最大網(wǎng)絡(luò)流的基本思想很簡(jiǎn)單——從某個(gè)初始流開(kāi)始，反復(fù)的增加流的流量知道不能再改進(jìn)為止。最后得到的流將是一個(gè)最大流。
定理 設(shè) P 是網(wǎng)絡(luò) G 中從起點(diǎn)到終點(diǎn)滿足一下條件的一條路徑：
(a) 對(duì)P中的每條正向邊(i,j)， Fij < Cij
(b)對(duì)P中的每條反向邊(i,j)， Fij > 0
設(shè) D是由P中所有正向邊(i,j)對(duì)應(yīng)的數(shù)和P中所有反向邊(i,j)對(duì)應(yīng)的數(shù)組成。
Δ =min D
Fij 如果(i,j)不在P中
F*ij={ Fij+ Δ 如果(i,j)在P中且是正向的
Fij-Δ 如果(i,j)在P中且不是正向的
根據(jù)上述定理，如果找不到路徑滿足上述定理，那么得到的流便是最大的。我們可以構(gòu)造一個(gè)算法：
1.從一個(gè)流開(kāi)始；
2.尋找一個(gè)滿足上述定理的路徑，如果這樣的路徑不存在，則停止，流是最大的；
3.將流過(guò)這條路徑的流量增加△，轉(zhuǎn)到第2行。
Ford-Fulkerson方法是按照上述定理構(gòu)造，解決最大流問(wèn)題的有效方法，一般采用深搜策略；而Edmonds-Karp算法是Ford-Fulkerson方法的廣搜的實(shí)現(xiàn)；相對(duì)而言，后者的效率稍微高一些。
下面是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];//存儲(chǔ)一次BFS遍歷之后流的可改進(jìn)量；
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]; /**/////存儲(chǔ)當(dāng)前已訪問(wèn)過(guò)的節(jié)點(diǎn)的增廣路徑；
41 while((step=bfs(mat,start,end,path)) != -1)//找不到增廣路徑時(shí)退出
42 {
43 maxflow += step;
44 cur=end;
45 while(cur != start)
46 {
47 pre=path[cur];
48 mat[pre][cur] -= step; //更新正向邊的實(shí)際容量
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