最近大三學生讓我去講課，我就惡補了最大流算法，筆者認為最重要的是讓學弟學妹們入門，知道算法怎麼來的？為什麼是這樣？了解的話提出自己的改進，然後再看看Dinic、SAP和ISAP算法…..
一、概念引入
首先要先清楚最大流的含義，就是說從源點到經過的所有路徑的最終到達彙點的所有流量和。
流網絡G=(V,E)是一個有向圖，其中每條邊(u,v)∈E均有一個非負容量c(u,v)>=0。如果(u,v)不屬于E，則假定c(u,v)=0。流網絡中有兩個特别的頂點：源點s和彙點t。下圖展示了一個流網絡的執行個體（其中斜線左邊的數字表示實際邊上的流，右邊的數字表示邊的最大容量）：
二、基礎知識準備
對一個流網絡G=(V,E)，其容量函數為c，源點和彙點分别為s和t。G的流f滿足下列三個性質：
容量限制：對所有的u，v∈V，要求f(u,v)<=c(u,v)。
反對稱性：對所有的u，v∈V，要求f(u,v)=-f(v,u)。
流守恒性：對所有u∈V-{s,t}，要求∑f(u,v)=0 (v∈V)。
容量限制說明了從一個頂點到另一個頂點的網絡流不能超過設定的容量，就好像是一個管道隻能傳輸一定容量的水，而不可能超過管道體積的限制；反對稱性說明了從頂點u到頂點v的流是其反向流求負所得，就好像是當參考方向固定後，站在不同的方向看，速度一正一負；而流守恒性說明了從非源點或非彙點的頂點出發的點網絡流之和為0，這有點類似于基爾霍夫電流定律，且不管什麼是基爾霍夫電流定律，通俗的講就是進入一個頂點的流量等于從該頂點出去的流量，如果這個等式不成立，必定會在該頂點出現聚集或是枯竭的情況，而這種情況是不應該出現流網絡中的，是以一般的最大流問題就是在不違背上述原則的基礎上求出從源點s到彙點t的最大的流量值，顯然這個流量值應該定義為從源點出發的總流量或是最後聚集到t的總流量，即流f的值定義為|f|=∑f(s,v) (v∈V)。
在求解最大流的問題前，必須對三個概念有所了解：殘留網絡，增廣路徑和割。下面先給出這三個概念的基本内容。
a.在給定的流網絡G=(V,E)中，設f為G中的一個流，并考察一對頂點u，v∈V，在不超過容量c(u,v)的條件下，從u到v之間可以壓入的額外網絡流量，就是(u,v)的殘留容量，就好像某一個管道的水還沒有超過管道的上限，那麼就這條管道而言，就一定還可以注入更多的水。殘留容量的定義為：cf(u,v)=c(u,v)-f(u,v)。而由所有屬于G的邊的殘留容量所構成的帶權有向圖就是G的殘留網絡。下圖就是上面的流網絡所對應的殘留網絡：
殘留網絡中的邊既可以是E中邊，也可以是它們的反向邊。隻有當兩條邊(u,v)和(v,u)中，至少有一條邊出現在初始網絡中時，邊(u,v)才會出現在殘留網絡中。下面是一個有關殘留網絡的定理，若f是G中的一個流，Gf是由G導出的殘留網絡，f'是Gf中的一個流，則f+f'是G中一個流，且其值|f+f'|=|f|+|f'|。證明時隻要證明f+f'這個流在G中滿足之前所講述的三個原則即可。在這裡隻給出了解性的證明，可以想象如果在一個管道中流動的水的總流量為f，而在該管道剩餘的流量中存在一個流f'可以滿足不會超過管道剩餘流量的最大限，那麼将f和f'合并後，也必定不會超過管道的總流量，而合并後的總流量值也一定是|f|+|f'|。
b.增廣路徑p為殘留網絡Gf中從s到t的一條簡單路徑。根據殘留網絡的定義，在不違反容量限制的條件下，G中所對應的增廣路徑上的每條邊(u,v)可以容納從u到v的某額外正網絡流。而能夠在這條路徑上的網絡流的最大值一定是p中邊的殘留容量的最小值。這還是比較好了解的，因為如果p上的流大于某條邊上的殘留容量，必定會在這條邊上出現流聚集的情況。是以我們将最大量為p的殘留網絡定義為：cf(p)=min{cf(u,v) | (u,v)在p上}。而結合之前在殘留網絡中定理，由于p一定是殘留網絡中從s到t的一條路徑，且|f'|=cf(p)，是以若已知G中的流f，則有|f|+|cf(p)|>|f|且|f|+|cf(p)|不會超過容量限制。
c.流網絡G(V,E)的割(S,T)将V劃分成為S和T=V-S兩部分，使得s∈S，t∈T。如果f是一個流，則穿過割(S,T)的淨流被定義為f(S,T)=∑f(x,y) (x∈S,y∈T)，割(S,T)的容量為c(S,T)。一個網絡的最小割就是網絡中所有割中具有最小容量的割。設f為G中的一個流，且(S,T)是G中的一個割，則通過割(S,T)的淨流f(S,T)=|f|。因為f(S,T)=f(S,V)-f(S,S)=f(S,V)=f(s,V)+f(S-s,V)=f(s,V)=|f|（這裡的公式根據f(X,Y)=∑f(x,y) (x∈X,y∈Y)的定義，以及前面的三個限制應該還是可以推出來的，這裡就不細講了）。有了上面這個定理，我們可以知道當把流不斷增大時，流f的值|f|不斷的接近最小割的容量直到相等，如果這時可以再增大流f，則f必定會超過某個最小的割得容量，則就會存在一個f(S,T)<=c(S,T)<|f|，顯然根據上面的定理這是不可能。是以最大流必定不超過網絡最小割的容量。
綜合上面所講，有一個很重要的定理：最大流最小割定理
如果f是具有源s和彙點t的流網絡G=(V,E)中的一個流，則下列條件是等價的：
1) f是G中一個最大流。
2) 殘留網絡Gf不包含增廣路徑。
3) 對G的某個割(S,T)，有|f|=c(S,T)。
三、代碼實作
不想寫一個Java版本的了。remnant 殘量。
#include <iostream>
#include <queue>
#include<string.h>
using namespace std;
#define arraysize 201
int maxData = 0x7fffffff;
int capacity[arraysize][arraysize]; //記錄殘留網絡的容量
int flow[arraysize]; //标記從源點到目前節點實際還剩多少流量可用
int pre[arraysize]; //标記在這條路徑上目前節點的前驅,同時标記該節點是否在隊列中
int n,m;
queue<int> myqueue;
int BFS(int src,int des)
{
int i,j;
while(!myqueue.empty()) //隊列清空
myqueue.pop();
for(i=1;i<m+1;++i)
{
pre[i]=-1;
}
pre[src]=0;
flow[src]= maxData;
myqueue.push(src);
while(!myqueue.empty())
{
int index = myqueue.front();
myqueue.pop();
if(index == des) //找到了增廣路徑
break;
for(i=1;i<m+1;++i)
{
if(i!=src && capacity[index][i]>0 && pre[i]==-1)
{
pre[i] = index; //記錄前驅
flow[i] = min(capacity[index][i],flow[index]); //關鍵：疊代的找到增量
myqueue.push(i);
}
}
}
if(pre[des]==-1) //殘留圖中不再存在增廣路徑
return -1;
else
return flow[des];
}
int maxFlow(int src,int des)
{
int increasement= 0;
int sumflow = 0;
while((increasement=BFS(src,des))!=-1)
{
int k = des; //利用前驅尋找路徑
while(k!=src)
{
int last = pre[k];
capacity[last][k] -= increasement; //改變正向邊的容量
capacity[k][last] += increasement; //改變反向邊的容量
k = last;
}
sumflow += increasement;
}
return sumflow;
}
int main()
{
int i,j;
int start,end,ci;
while(cin>>n>>m)
{
memset(capacity,0,sizeof(capacity));
memset(flow,0,sizeof(flow));
for(i=0;i<n;++i)
{
cin>>start>>end>>ci;
if(start == end) //考慮起點終點相同的情況
continue;
capacity[start][end] +=ci; //此處注意可能出現多條同一起點終點的情況
}
cout<<maxFlow(1,m)<<endl;
}
return 0;
}
用的時候自己修改一下。
bool EK_Bfs (int start, int end)//廣搜用于找增廣路；
{
bool flag[Maxn];//标記數組
memset (flag, false, sizeof(flag));
memset (p, -1, sizeof(p));
flag[start] = true;
queue t;
t.push(start);
while (!t.empty())
{
int top = t.front();
if (top == end)return true;// 此時找到增廣路
t.pop();
for (int i=1; i<=n; i++)
{
if (map[top][i] && !flag[i])
{
flag[i] = true;
t.push(i);
p[i] = top;// 記錄前驅（很關鍵）
}
}
}
return false;
}
int E_K (int start,int end)
{
int u,max = 0,mn;//max用來初始化最大流為0;
while (EK_Bfs(start,end))//當增廣成功時
{
mn = 100000;
u = end;
while (p[u] != -1)//尋找”瓶頸“邊，并且記錄容量;
{
mn = min (mn, map[p[u]][u]);
u = p[u];
}
max += mn;//累加邊的最大流;
u = end;
while (p[u] != -1)//修改路徑上的邊容量；
{
map[p[u]][u] -= mn;
map[u][p[u]] += mn;
u = p[u];
}
}
return max;
}