問題表述：給定一幅圖（n個結點，m條邊），每一條邊有一個容量，現在需要將一些物品從結點s（稱為源點）運送到結點t（稱為匯點），可以從其他結點中轉，求最大的運送量。

在介紹最大流問題的解決方法之前，先介紹幾個概念.

網絡：網絡是一個有向帶權圖，包含一個源點和一個匯點，沒有反向平行邊。

網絡流：網絡流即網上的流，是定義在網絡邊集E上的一個非負函數flow={flow（u，v）}, flow（u,v）是邊上的流量。

可行流：滿足以下兩個性質的網絡流flow稱為可行流。

容量約束：每條邊的實際流量不能超過改變的最大流量。

流量守恒：除了源點s和匯點t之外，所有內部節點流入量等于流出量。

源點s：源點主要是流出，但也有可能流入。

源點的凈輸出值=流出量之和-流入量之和。

匯點t：匯點主要是流入，但也有可能流出。

匯點的凈輸入值=流入量之和-流出量之和。

對于一個網絡可行流flow，凈輸出等于凈輸入，這仍然是流量守恒。

網絡最大流：在滿足容量約束和流量守恒的前提下，在流網絡中找到一個凈輸出最大的網絡流。

反向弧：若從u到v的邊的容量為c ，這條邊上有流量 f 流過（稱為正向弧），則相當于v到u有一條容量為0的邊，其流量為- f ，這條邊就是反向弧。反向弧的作用主要是用于尋找增廣路。

反向弧的意義：反向弧的作用是起到有更優決策的時候會使當前選擇的弧會自動放棄。反向弧有流量的原因是因為如果剛剛選擇了正向弧，下一次如果存在更優策略使這f的流量流入匯點，就可以選擇反向弧，將流量 f 撤銷。

殘余網絡：計算出圖中的每條邊上容量與流量之差（稱為殘余容量），即可得到殘余網絡。注意由于反向邊的存在，殘余網絡中的邊數可能到達原圖中邊數的兩倍。

觀察圖下圖，這種狀態下它的殘余網絡。

增廣路徑：殘余網絡中任何一條從s到t的有向道路都對應一條原圖中的增廣路徑 —— 只要求出該道路中所有殘量的最小值d ，把對應的所有邊上的流量增加d 即可，這個過程稱為增廣。

最大流定理：如果殘留網絡上找不到增廣路徑，則當前流為最大流；反之，如果當前流不為最大流，則一定有增廣路徑。

這樣的話，求解最大流就只需要在殘余網絡中尋找增廣路，直到不存在可以從s流向t 的增廣路，此時即為最大流。求解最大流問題的高效算法有 dinic,sap和isap。

我們今天講最基礎的FF算法與EK算法，他倆的區別在于一個是DFS找增廣路，一個是BFS找增廣路。后者高效一點。

Edmonds-Karp算法：以廣度優先的增廣路算法，又稱為最短增廣路算法（Shortest Augument Panth, SAP）。

最短增廣路算法步驟：采用隊列q 來存放已訪問未檢查的結點。布爾數組vis[]標識結點是否被訪問過，pre[]數組記錄可增廣路上結點的前驅。pre[v]=u 表示可增廣路上v 結點的前驅是u，最大流值maxflow=0。

初始化可行流flow 為零流，即實流網絡中全是零流邊，殘余網絡中全是最大容量邊（可增量）。初始化vis[]數組為false，pre[]數組為?1。

令vis[s]=true，s 加入隊列q。

如果隊列不空，繼續下一步，否則算法結束，找不到可增廣路。當前的實流網絡就是最大流網絡，返回最大流值maxflow。

隊頭元素new 出隊，在殘余網絡中檢查new 的所有鄰接結點i。如果未被訪問，則訪問之，令vis[i]=true，pre[i]=new；如果i=t，說明已到達匯點，找到一條可增廣路，轉向第（5）步；否則結點i 加入隊列q，轉向第（3）步。

從匯點開始，通過前驅數組pre[]，逆向找可增廣路上每條邊值的最小值，即可增量d。

在實流網絡中增流，在殘余網絡中減流，Maxflow+=d，轉向第（2）步。

?這里給出EK算法模板：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <queue> #define INF 0x3f3f3f3f using namespace std; int n,m; const int maxn=1005; int g[maxn][maxn];//容量 int f[maxn][maxn];//流量 bool vis[maxn]; int pre[maxn]; bool bfs(int s,int t){memset(pre,-1,sizeof pre);memset(vis,false,sizeof vis);queue<int> q;vis[s]=true;q.push(s);while(!q.empty()){int now=q.front();q.pop();for(int i=1;i<=n;i++){if(!vis[i]&&g[now][i]){vis[i]=true;pre[i]=now;if(i==t) return true;q.push(i);}}}return false; } int EK(int s,int t){int maxflow=0;int u,v;while(bfs(s,t)){int d=INF;v=t;while(v!=s){u=pre[v];if(d>g[u][v])d=g[u][v];v=u;}maxflow+=d;v=t;while(v!=s){u=pre[v];g[u][v]-=d;g[v][u]+=d;if(f[v][u]>0)f[v][u]-=d;else f[u][v]+=d;v=u;}}return maxflow; } int main() {//int s,t;int u,v,c;while(~scanf("%d%d",&m,&n)){memset(f,0,sizeof f);memset(g,0,sizeof g);for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&c);g[u][v]+=c;}printf("%d\n",EK(1,n));}return 0; }

?

?

總結

以上是生活随笔為你收集整理的图论--网络流最大流问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。