最近又復(fù)習(xí)了下最大流問(wèn)題，每次看這部分的內(nèi)容都會(huì)有新的收獲。可以說(shuō)最大流問(wèn)題的資料網(wǎng)上一搜一大把，根本沒(méi)有必要自己寫；但是大部分資料上的專業(yè)術(shù)語(yǔ)太多了，初學(xué)很難理解，至少我當(dāng)年學(xué)這部分的時(shí)候前幾次就沒(méi)有看懂。所以我準(zhǔn)備備份一點(diǎn)個(gè)人的理解。
圖-1
如圖-1所示，在這個(gè)運(yùn)輸網(wǎng)絡(luò)中，源點(diǎn)S和匯點(diǎn)T分別是1,7，各邊的容量為C(u,v)。圖中紅色虛線所示就是一個(gè)可行流。標(biāo)準(zhǔn)圖示法如圖-2所示：
其中p(u,v) / c(u,v)分別表示該邊的實(shí)際流量與最大容量。
關(guān)于最大流
熟悉了什么是網(wǎng)絡(luò)流，最大流也就很好理解了。就是對(duì)于任意的u∈V-{s},使得p(s,u)的和達(dá)到最大。上面的運(yùn)輸網(wǎng)絡(luò)中，最大流如圖-3所示：MaxFlow=p(1,2)+p(1,3)=2+1=3。
在介紹最大流問(wèn)題之前，先介紹幾個(gè)概念：殘余網(wǎng)絡(luò)，增廣路徑，反向弧，最大流定理以及求最大流的Ford-Fulkerson方法。
殘余網(wǎng)絡(luò) 增廣路徑 反向弧
觀察下圖-4，這種狀態(tài)下它的殘余網(wǎng)絡(luò)如圖-5所示：
也許現(xiàn)在你已經(jīng)知道什么是殘余網(wǎng)絡(luò)了，對(duì)于已經(jīng)找到一條從S 到T的路徑的網(wǎng)絡(luò)中，只要在這條路徑上，把C(u,v)的值更新為C(u,v)-P(u,v)，并且添加反向弧C(v,u)。對(duì)應(yīng)的增廣路徑Path為殘留網(wǎng)絡(luò)上從S到T的一條簡(jiǎn)單路徑。圖-4中1，2，4，7就是一條增廣路徑，當(dāng)然還有1，3，4，7。
此外在未做任何操作之前，原始的有向圖也是一個(gè)殘余網(wǎng)絡(luò)，它僅僅是未做任何更新而已。
最大流定理
如果殘留網(wǎng)絡(luò)上找不到增廣路徑，則當(dāng)前流為最大流；反之，如果當(dāng)前流不為最大流，則一定有增廣路徑。
Ford-Fulkerson方法
介紹完上面的概念之后，便可以用Ford-Fulkerson方法求最大流了。為什么叫Ford-Fulkerson方法而不是算法，原因在于可以用多種方式實(shí)現(xiàn)這一方法，方式并不唯一。下面介紹一種基于廣度優(yōu)先搜索(BFS)來(lái)計(jì)算增廣路徑P的算法：Edmonds-Karp算法。
算法流程如下：
設(shè)隊(duì)列Q：存儲(chǔ)當(dāng)前未訪問(wèn)的節(jié)點(diǎn)，隊(duì)首節(jié)點(diǎn)出隊(duì)后，成為已檢查的標(biāo)點(diǎn)；
Path數(shù)組：存儲(chǔ)當(dāng)前已訪問(wèn)過(guò)的節(jié)點(diǎn)的增廣路徑；
Flow數(shù)組：存儲(chǔ)一次BFS遍歷之后流的可改進(jìn)量；
Repeat:
Path清空；
源點(diǎn)S進(jìn)入Path和Q，Path[S]<-0，Flow[S]<-+∞；
While Q非空 and 匯點(diǎn)T未訪問(wèn) do
Begin
隊(duì)首頂點(diǎn)u出對(duì)；
For每一條從u出發(fā)的弧(u,v) do
If v未訪問(wèn) and 弧(u,v) 的流量可改進(jìn)；
Then Flow[v]<-min(Flow[u],c[u][v]) and v入隊(duì) and Path[v]<-u；
End while
If(匯點(diǎn)T已訪問(wèn))
Then 從匯點(diǎn)T沿著Path構(gòu)造殘余網(wǎng)絡(luò)；
Until 匯點(diǎn)T未被訪問(wèn)
應(yīng)用實(shí)例
這是一道最大流的入門題，題目如下：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
Description
Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.
Input
The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.
Output
For each case, output a single integer, the maximum rate at which water may emptied from the pond.
Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
Sample Output
50
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4
5 const int N = 210;
6 const int INF = 0x7FFFFFFF;
7 int n,m,map[N][N],path[N],flow[N],start,end;
8 queue<int> q;
9
10 int bfs(){
11 int i,t;
12 while(!q.empty()) q.pop();
13 memset(path,-1,sizeof(path));
14 path[start]=0,flow[start]=INF;
15 q.push(start);
16 while(!q.empty()){
17 t=q.front();
18 q.pop();
19 if(t==end) break;
20 for(i=1;i<=m;i++){
21 if(i!=start && path[i]==-1 && map[t][i]){
22 flow[i]=flow[t]<map[t][i]?flow[t]:map[t][i];
23 q.push(i);
24 path[i]=t;
25 }
26 }
27 }
28 if(path[end]==-1) return -1;
29 return flow[m]; //一次遍歷之后的流量增量
30 }
31 int Edmonds_Karp(){
32 int max_flow=0,step,now,pre;
33 while((step=bfs())!=-1){ //找不到增路徑時(shí)退出
34 max_flow+=step;
35 now=end;
36 while(now!=start){
37 pre=path[now];
38 map[pre][now]-=step; //更新正向邊的實(shí)際容量
39 map[now][pre]+=step; //添加反向邊
40 now=pre;
41 }
42 }
43 return max_flow;
44 }
45 int main(){
46 int i,u,v,cost;
47 while(scanf("%d %d",&n,&m)!=EOF){
48 memset(map,0,sizeof(map));
49 for(i=0;i<n;i++){
50 scanf("%d %d %d",&u,&v,&cost);
51 map[u][v]+=cost; //not just only one input
52 }
53 start=1,end=m;
54 printf("%d\n",Edmonds_Karp());
55 }
56 return 0;
57 }
58