一、什么是網絡流

網絡流是指給定一個有向圖，其中有兩個特殊的點：源點 $s$（Source）和匯點 $t$（Sink）；每條邊都有一個指定的流量上限，下文均稱之為容量（Capacity），即經過這條邊的流量不能超過容量，這樣的圖被稱為網絡流圖。同時，除了源點和匯點外，所有點的入流和出流都相等，源點只有流出的流，匯點只有流入的流，網絡流就是從 $s$ 到 $t$ 的一個可行流。

二、可行流、最大流

定義 $c(u,v)$ 表示邊 $(u,v)$ 的容量，$f(u,v)$ 表示邊 $(u,v)$ 的流量。如果滿足 $0\le f(u,v)\le c(u,v)$，則稱$f(u,v)$ 為邊 $(u,v)$ 上的流量。

如果有一組流量滿足：源點 $s$ 的流出量等于整個網絡的流量，匯點 $t$ 的流入量等于整個網絡的流量，除了任意一個不是 $s$ 或 $t$ 的點的總流入量等于總流出量。那么整個網絡中的流量被稱為一個可行流。

在所有可行流中，最大流指其中流量最大的一個流的流量。

三、相關定義

源點 $s$：只有流出量的點。

匯點 $t$：只有流入量的點。

容量 $c$：$c(u,v)$ 表示邊 $(u,v)$ 上的容量。

流量 $f$：$f(u,v)$ 表示邊 $(u,v)$ 上的流量。

殘量 $w$：$w(u,v)$ 表示邊 $(u,v)$ 上的殘量（顯然有 $w(u,v)=c(u,v)?f(u,v)$）。

四、網絡流的性質

1.容量限制
對于任何一條邊，都有 $0\le f(u,v)\le c(u,v)$。

2.斜對稱性
對于任何一條邊，都有 $f(u,v)=?f(v,u)$。即從 $u$ 到 $v$ 的流量一定等于從 $v$ 到 $u$ 的流量的相反數。

3.流守恒性
對于任何一個點 $u$，如果滿足 $u=s$ 并且 $u=t$，那么一定有 $\sum f(u,v)=0$，即 $u$ 到相鄰節點的流量之和為 $0$。因為 $u$ 本身不會制造和消耗流量。

五、最大流的求解

增廣路思想

找到一條從 $s$ 到 $t$ 的路徑，使得路徑上的每一條邊都有 $w(u,v)>0$ 即殘量大于 $0$。注意：這里是嚴格 $>$ 而不是$\ge$，這意味著這條邊還可以分配流量。這條路徑就被叫做増廣路。

找到這條路徑上最小的 $w(u,v)$，記為 $flow$。將這條路徑上的每一條邊的$w(u,v)$ 減去 $flow$。

重復上述過程，直到找不到増廣路為止。

不防依照這個思想先模擬一遍：

如果我們把每條邊的的信息用殘量 / 容量表示出來，可以得到下圖：

假設我們第一次找到的増廣路為$1?2?3?4$，那么我們把這條路徑上的邊的 $w(u,v)$ 減去 $minf(u,v)$ 即 $1$，得到下圖：

然后我們發現已經沒有増廣路了，此時算出來的“最大流”為 1。但是我們可以手動計算一下，這張圖的最大流其實是 2。這個最大流的路徑為 $1?2?4$（流量為 $1$）和 $1?3?4$（流量為 $1$）。

因此，我們可以發現這樣的過程是錯誤的。原因就是増廣路在一定意義上是有順序的，說白了就是沒有給它反悔的機會。所以接下來我們要引入反向邊的概念。

反向邊思想
通過上文的分析我們已經知道，當我們在尋找増廣路的時候，找到的并不一定是最優解。如果我們對正向邊的 $w(u,v)$ 減去 $flow$ 的同時，將對應的反向邊的 $w(v,u)$ 加上 $flow$，我們就相當于可以反悔從這條邊流過。

那么我們可以建立反向邊，初始時每條邊的 $w(u,v)=c(u,v)$，它的反向邊的 $w(v,u)=0$（顯然反向邊不能有流量，因此殘量為 $0$）。

接下來再看一下上面那個例子，我們只用 $w(u,v)$ 來表示每條邊（包括反向邊）的信息：

接下來開始尋找増廣路，假如還是 $1?2?3?4$ 這條路徑。

我們需要把 $w(1,2)$，$w(2,3)$，$w(3,4)$ 減少 $1$，同時把反向邊的 $w(2,1)$，$w(3,2)$，$w(4,3)$ 增加 1。那么可以得到下圖：

繼續從 $s$ 開始尋找増廣路（不需要考慮邊的類型），顯然可以發現路徑 $1?3?2?4$，其中 $flow=1$。更新邊的信息，得到下圖：

此時我們發現沒有増廣路了，為了直觀觀察這個網絡，我們去掉反向邊，顯然我們求出的最大流為 2

正確性
當我們第二次増廣邊 $(2,3)$ 走這條反向邊 $(3,2)$ 時，把 $(2,3)$ 和 $(3,2)$ 的流量抵消了，相當于把 $(2,3)$ 這條正向邊的流量給退了回去使得可以不走 $(2,3)$ 這條邊。

如果反向邊 $(v,u)$ 的流量不能完全抵消正向邊 $(u,v)$，那么意味著從 $u$ 開始還可以流一部分流量到 $v$，這樣也是允許的。

思路總結

最初這個網絡的流量為 0，稱為零流。

找到一條從 $s$ 到 $t$ 的路徑，使得路徑上的每一條邊都有 $w(u,v)>0$ 即殘量大于 $0$。注意：這里是嚴格 $>$ 而不是$\ge$，這意味著這條邊還可以分配流量。這條路徑就被叫做増廣路。

找到這條路徑上最小的 $w(u,v)$，記為 $flow$。

將這條路徑上的每一條邊的 $w(u,v)$ 減去 $flow$，同時將反向邊 $(v,u)$ 的 $w(v,u)$ 加上 $flow$。

重復上述過程，直到找不到増廣路為止，此時的流量就是最大流。

六、算法實現

最大流算法主要有兩類，增廣路算法和預留推進算法，下面介紹的兩種算法都屬于增廣路算法。
增廣路算法都是基于增廣路定理（Augmenting Path Theorem）：網絡達到最大流當且僅當殘留網絡中沒有増廣路。

• Ford-Fulkerson（FF算法）
  思路：增廣路思想的完全模擬，它通過深度優先搜索來尋找增廣路，并沿著它增廣，直到找不到增廣路為止。
  老規矩，上代碼之前先來道模板題：【模板】網絡最大流
  c++代碼：

#include <bits/stdc++.h> using namespace std; const int maxn=1e5+7,inf=0x3f3f3f3f; int n,m,s,t; bool used[maxn]; //DFS中用到的訪問標記 struct node{ //用于表示邊的結構體（終點、容量、反向邊）int to,cap,rev; }; vector<node> v[maxn]; //圖的鄰接表表示 void add(int from,int to,int cap){ //向圖中增加一條從from到to容量為cap的邊v[from].push_back((node){to,cap,v[to].size()});v[to].push_back((node){from,0,v[from].size()-1}); } int dfs(int x,int t,int f){ //通過DFS尋找增廣路if(x==t) return f;used[x]=true;for(int i=0;i<v[x].size();i++){node &e=v[x][i];if(!used[e.to]&&e.cap>0){int d=dfs(e.to,t,min(f,e.cap));if(d>0){e.cap-=d;v[e.to][e.rev].cap+=d;return d;}}}return 0; } int Ford_Fulkerson(int s,int t){ //求解從s到t的最大流int flow=0;while (1){memset(used,false,sizeof(used));int f=dfs(s,t,inf);if(!f) return flow;flow+=f;}}int main(){cin>>n>>m>>s>>t;while(m--){int x,y,z;cin>>x>>y>>z;add(x,y,z);}cout<<Ford_Fulkerson(s,t);return 0; }

時間復雜度：記最大流的流量為$F$，那么$Fork?fulkerson$算法最多進行$F$次深度優先搜索，所以其復雜度為$O(F|E|)$。不過，這是一個很松的上界，達到這種最壞復雜度的情況幾乎不存在。所以在多數情況下，即便通過估算得到的復雜度偏高，實際運用當中也還是比較快的。

• Dinic
  思路：與$FF$算法相對，$Dinic$算法總是尋找最短的增廣路，并沿著它增廣。因為最短增廣路的長度在增廣過程中始終不會變短，所以無需每次都通過深度預先搜索來尋找最短增廣路，我們可以先進行一次寬度優先搜索，然后考慮由近距離頂點指向遠距離頂點的邊所組成的分層圖，在上面進行深度優先搜索尋找最短增廣路。如果在分層圖上找不到新的增廣路了，則說明最短增廣路的長度確實變長了，或不存在增廣路了，于是重新通過寬度優先搜索構造新的分層圖。此外，還可以對這個算法進行優化。
  當前弧優化：在每次對分層圖進行深度優先搜索尋找增廣路時，避免對一條沒有用的邊進行多次檢查。
  c++代碼：

#include <bits/stdc++.h> using namespace std; const int maxn=1e5+7,inf=0x3f3f3f3f; int n,m,s,t,level[maxn],iter[maxn]; //level：頂點到源點的距離標號 iter：當前弧，在其之前的邊已經沒有用了 struct node{int to,cap,rev; }; vector<node> v[maxn]; void add(int from,int to,int cap){v[from].push_back((node){to,cap,v[to].size()});v[to].push_back((node){from,0,v[from].size()-1}); } int bfs(int s){ //通過BFS計算從源點出發的距離標號memset(level,0,sizeof(level));queue<int> q;level[s]=1;q.push(s);while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<v[x].size();i++){node e=v[x][i];if(e.cap&&!level[e.to]){level[e.to]=level[x]+1;q.push(e.to);}}}return level[t]; } int dfs(int x,int t,int f){ //通過DFS尋找增廣路if(x==t) return f;for(int &i=iter[x];i<v[x].size();i++){node &e=v[x][i];if(e.cap&&level[x]<level[e.to]){int d=dfs(e.to,t,min(f,e.cap));if(d){e.cap-=d;v[e.to][e.rev].cap+=d;return d;}}}return 0; } int Dinic(int s,int t){ //求解從s到t的最大流int flow=0;while(bfs(s)){memset(iter,0,sizeof(iter));int f;while((f=dfs(s,t,inf))){flow+=f;}}return flow; } int main(){cin>>n>>m>>s>>t;while(m--){int x,y,z;cin>>x>>y>>z;add(x,y,z);}cout<<Dinic(s,t);return 0; }

時間復雜度：每一步構造分層圖的復雜度為$O(|E|)$，加入當前弧優化后，可以保證對每次分層圖進行深度優先搜索復雜度為$O(|E||V|)$，而每一步完成之后最短增廣路的長度都會至少增加1，由于增廣路的長度不會超過$|V|?1$，因此最多重復O(|V|)步就可以了，這樣總的復雜度就是$O(|E||V|$²)。不過，該算法在實際應用中速度非常快，很多時候即便圖的規模比較大也沒有問題。

• 兩種算法的對比
  評測記錄：
  
  第一個是Dinic算法，耗時470ms，第二個是FF算法，耗時1220ms。

總結：99%的網絡流算法，都可以用Dinic去解。卡Dinic的毒瘤出題人，都是*嗶*

不好意思爆粗口了，不過，還真的有這種毒瘤出題人💢，👇👇👇👇👇
【模板】最大流 加強版 / 預流推進
解決這道題就必須要用我上面說的第二種最大流算法：預流推進法。
但是我太懶（蒻）了，現在并不想去寫那種算法，就交給你們了QWQ

七.最大流的應用

洛谷P1345奶牛的電信
做這道題之前，先說一個很重要的定理：
最大流最小割定理：最大流等于最小割。
那么，最小割又是什么呢？最小割是要求為了使原點（記為S）和匯點（記為T）不連通，最少要割幾條邊。
好了，你是不是覺得你可以去做這道題了（其實說的就是我 ），裸的割邊，打個Dinic就行了，但有時候我們還是太naive了。
重新讀題，會發現這題割的不是邊，是點。所以說，我們需要一個割邊轉割點的小技巧。
我們可以考慮“拆點”，即把一個點拆成兩個點，中間連一條邊權為1的邊。
前一個點作為“入點”，別的點連邊連入這里。
后一個點作為“出點”，出去的邊從這里出去。
這樣，只要我們切斷中間那條邊，就可以等效于除去這個點，如圖：

紅色的邊邊權為1，黑色的邊邊權為$inf$。

原點和匯點的內部邊權為$inf$，因為顯然這兩個點不能刪除。

題面給的邊刪除沒意義（因為我們要刪點），所以也設為inf(事實上設為1也沒問題，因為刪除這條邊的權值可以理解為刪除了一個點)

至此，我們就可以把這道題AC了
c++代碼：

#include <bits/stdc++.h> using namespace std; const int maxn=1e5+7,inf=0x3f3f3f3f; int n,m,s,t,level[maxn],iter[maxn]; struct node{int to,cap,rev; }; vector<node> v[maxn]; void add(int from,int to,int cap){v[from].push_back((node){to,cap,v[to].size()});v[to].push_back((node){from,0,v[from].size()-1}); } int bfs(int s){memset(level,0,sizeof(level));queue<int> q;level[s]=1;q.push(s);while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<v[x].size();i++){node e=v[x][i];if(e.cap&&!level[e.to]){level[e.to]=level[x]+1;q.push(e.to);}}}return level[t]; } int dfs(int x,int t,int f){if(x==t) return f;for(int &i=iter[x];i<v[x].size();i++){node &e=v[x][i];if(e.cap&&level[x]<level[e.to]){int d=dfs(e.to,t,min(f,e.cap));if(d){e.cap-=d;v[e.to][e.rev].cap+=d;return d;}}}return 0; } int Dinic(int s,int t){int flow=0;while(bfs(s)){memset(iter,0,sizeof(iter));int f;while((f=dfs(s,t,inf))){flow+=f;}}return flow; } int main(){cin>>n>>m>>s>>t;for(int i=1;i<=n;i++){if(i==s||i==t){add(i,i+n,inf);}else add(i,i+n,1);}while(m--){int x,y;cin>>x>>y;add(x+n,y,inf);add(y+n,x,inf);}cout<<Dinic(s,t);return 0; }

總結

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

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