本blog重點是代碼

• 網絡流的相關概念
• • 流網絡(flow network)
  • 流(flow)
  • 網絡的流
  • 殘留網絡(residual network)
  • 增廣路徑(augmenting path)
• Edmonds-Karp
• • 算法思想
  • bfs模板
  • 調用EK&更新殘留網絡流模板
  • luogu的AC代碼(EK版)
• Dinic
• • 算法思路
  • 時間復雜度證明
  • bfs模板
  • • 模板1
    • 模板2
  • dfs模板
  • • 不帶弧優化模板（最好別用）
    • 帶弧優化模板
  • 不帶弧優化版AC代碼
  • 帶弧優化AC代碼
• ISAP
• • 算法思想
  • bfs模板
  • dfs模板
  • • 不帶弧優化
    • 帶弧優化
  • 不帶弧優化版AC代碼
  • 帶弧優化版AC代碼
• Update(僅模板)
• • 無源匯有上下界可行流
  • 有源匯有上下界最大流
  • 有源匯有上下界最小流

綜合了自己在網上看到的眾多博客，多種多樣，肯定有很多問題，歡迎各位Dalao指出

網絡流的相關概念

流網絡(flow network)

流網絡$G=(V,E)$是一個有向圖，其中每條邊$(u,v)$均有一非負容量$c(u,v)\ge 0$
流網絡中有兩個特殊的頂點: 源點s和匯點t
假定每個頂點都處于從源點到匯點的某條路徑上，就是說，對每個頂點v，存在一條路徑$s\to v\to t$
$G$為連通圖，且$|E|\ge |V|?1$

流(flow)

邊的流是一個實值函數f，滿足下列三個性質：
容量限制：對所有$u,v\in V$， 要求$f(u,v)\le c(u,v)$
理解：流量不會超過邊的容量
斜對稱性：對所有$u,v\in V$， 要求$f(u,v)=?f(v,u)$
理解：一個方向的流是其反方向流的相反數。這是完善的網絡流理論
不可缺少的，像用正負數來定義物理量一樣。
流守恒性：對所有$u,v\in V?s,t$，要求${\sum }_{v}f(u,v)?{\sum }_{w}f(w,u)=0$
理解：進入點u的總流量=離開點u的總流量

每條邊上斜線前的數字是流量，后的數字是容量

網絡的流

網絡的流定義為$f=\sum f(s,v)$
即，從源點s出發的總流

最大流問題就是給出一個源點和匯點的流網絡，希望找到從源點到匯點的最大值流

規定$f(u,v)$和$f(v,u)$最多只有一個正數（可以均為0）。若兩個均為正數，可以消減一個
方向的流量
舉個栗子：u給v三個蘋果，v如果又給u三個蘋果，那就相當于彼此之間沒有給過蘋果；u給v三個蘋果，v給u五個蘋果，就相當于v給u兩個蘋果。也就是說流如果都是正數，是可以相互抵消，達成協議的

殘留網絡(residual network)

邊的殘留容量：$r(u,v)=c(u,v)?f(u,v)$
殘留網絡一句話就是殘留邊所構成的一個網絡流，且每條邊的容量是嚴格為正的，即當$0<f(u,v)<c(u,v)=>r(u,v)=c(u,v)?f(u,v)>0$，這條邊$(u,v)$仍在殘留網絡中
👉
頂點1到2已經滿流，故1到2的殘留容量為0，但此時仍存在2到1的殘留容量

增廣路徑(augmenting path)

增廣路徑P為殘留網絡中從源點s到匯點t的一條簡單路徑
增廣路徑的殘留容量是：
$\delta (p)=minr(u,v):(u,v)\in P$
一句話就是這一條路徑上最小的邊流量
沿著路徑增廣是沿著路徑的每條邊發送$\delta (P)$單位的流。相應的，修改這一路徑上的流的值和殘留容量
$f=f+\delta (P)$
$r(u,v)=r(u,v)?\delta (P)$ $(u,v)\in P$
$r(v,u)=r(v,u)+\delta (P)$ $(u,v)\in P$

---

接下來的各個算法介紹的模板是基于luogu這道題的AC代碼，一定注意哦~~

Edmonds-Karp

算法思想

Edmonds–Karp算法是一種實用性很強的，實現簡潔的，基于增廣路思想的網絡流算法。
它的基本算法思想是：每次都找長度最短的增廣路徑

網絡圖的邊可看成長度均為1，因此可用BFS找從源點s到匯點t的最短路徑。
為了便于算出路徑的殘留容量，用一個數組$aug[v]$記錄從源點s到當前結點v這條路徑的殘留容量
在BFS時，從隊首結點u擴展出鄰接點v，則有：$aug[v]=min(aug[u],cap[u][v])$，$cap[u][v]$表示$(u,v)$這一條邊的殘留容量
顯然，BFS找出的一條增廣路徑的殘留容量為$aug[t]$

在找到一條增廣路徑的過后就要更新新的殘留容量

bfs模板

此代碼中的flow即是上文中的aug

int BFS ( int s, int t ) {//使用BFS尋找增廣路徑 while ( ! q.empty() )q.pop();memset ( pre, -1, sizeof ( pre ) );pre[s] = 0;flow[s] = INF;//初始化源點的流量設為無窮大 q.push( s );while ( ! q.empty() ) {int u = q.front();q.pop();if ( u == t )//抵達匯點，找到了增廣路徑 break;for ( int i = 1;i <= t;i ++ ) {//遍歷所有的點 //原圖是沒有流向s的流，但是在剩余網絡中有反向邊，故有流向s的流，所以要判斷 if ( i != s && r[u][i] > 0 && pre[i] == -1 ) {pre[i] = u;//記錄前驅以保存路徑 flow[i] = min ( r[u][i], flow[u] );//迭代地找到增量 q.push( i );}}}if ( pre[t] == -1 )//匯點沒有前驅節點，即殘余圖中無增廣路徑 return -1;return flow[t]; }

調用EK&更新殘留網絡流模板

int EK ( int s, int t ) {int max_flow = 0;int Flow = BFS ( s, t );while ( Flow != -1 ) {for ( int i = t;i != s;i = pre[i] ) {//利用前驅尋找路徑，做到更新殘留圖 r[pre[i]][i] -= Flow;//改變正向邊的容量 r[i][pre[i]] += Flow;//改變反向邊的容量 }max_flow += Flow;Flow = BFS ( s, t ); }return max_flow; }

---

luogu的AC代碼(EK版)

#include <queue> #include <cstdio> #include <cstring> using namespace std; #define MAXN 405 #define INF 0x7f7f7f7f queue < int > q; int n, m; int r[MAXN][MAXN];//記錄殘余網絡的容量 int flow[MAXN];//標記從源點到當前節點實際還剩多少流量 int pre[MAXN];//節點的前驅，同時標記點是否被標記過 int BFS ( int s, int t ) {//使用BFS尋找增廣路徑 while ( ! q.empty() )q.pop();memset ( pre, -1, sizeof ( pre ) );pre[s] = 0;flow[s] = INF;//初始化源點的流量設為無窮大 q.push( s );while ( ! q.empty() ) {int u = q.front();q.pop();if ( u == t )//抵達匯點，找到了增廣路徑 break;for ( int i = 1;i <= t;i ++ ) {//遍歷所有的點 //原圖是沒有流向s的流，但是在剩余網絡中有反向邊，故有流向s的流，所以要判斷 if ( i != s && r[u][i] > 0 && pre[i] == -1 ) {pre[i] = u;//記錄前驅以保存路徑 flow[i] = min ( r[u][i], flow[u] );//迭代地找到增量 q.push( i );}}}if ( pre[t] == -1 )//匯點沒有前驅節點，即殘余圖中無增廣路徑 return -1;return flow[t]; }int EK ( int s, int t ) {int max_flow = 0;int Flow = BFS ( s, t );while ( Flow != -1 ) {for ( int i = t;i != s;i = pre[i] ) {//利用前驅尋找路徑，做到更新殘留圖 r[pre[i]][i] -= Flow;//改變正向邊的容量 r[i][pre[i]] += Flow;//改變反向邊的容量 }max_flow += Flow;Flow = BFS ( s, t ); }return max_flow; }int main() {scanf ( "%d %d", &n, &m );for ( int i = 1;i <= n;i ++ ) {int si, ei, ci;scanf ( "%d %d %d", &si, &ei, &ci );r[si][ei] += ci;}printf ( "%d", EK ( 1, m ) );return 0; }

---

Dinic

算法思路

1、建立網絡（包括正向弧和反向弧（初始邊權為0）），將總流量置為0
2、構造層次網絡
層次網絡，簡單的說，就是求出每個點u的層次，u的層次是從源點到該點的最短路徑（注意：這個最短路是指弧的權都為1的情況下的最短路），若與源點不連通，層次置為-1，只用一遍bfs即可
3、判斷匯點的層次是否為-1
是：算法結束，輸出當前的總流量
否：下一步
4、用一次dfs實現所有增廣
增廣：通過dfs找的增廣路，找到了之后，將每條邊的權都減去該增廣路中擁有最小流量的邊的流量，將每條邊的反向邊的權增加這個值，同時將總流量加上這個值
dfs直到找不到一條可行的從原點到匯點的路
5、重復步驟2

---

細節處理，如果不是用二維結構體以下標來表示邊，而是一維數組以邊的編號為下標
如何快速找到一條邊的反向邊：邊的編號從0開始，反向邊加在正向邊之后，反向邊即為該點的編號異或1
我提供的代碼里是以2開始的，寫法問題，別介意
復雜度：理論上來說，應該是$O(n^2?m)$，n表示點數，m表示邊數，然而實際上，很難卡到那個復雜度

---

弧優化
在DFS的時候記錄當前已經計算到第幾條邊了，避免重復計算
然后在下一次構建層次網絡的注意將head數組還原
溫馨提醒：我們所說的Dinic時間復雜度是建立在運用了弧優化的基礎上，所以如果你不用弧優化，這個時間復雜度就。。。

時間復雜度證明

與最短增廣路算法一樣，Dinic算法最多被分為n個階段，每個階段包括建層次網絡和尋找增廣路兩部分，其中建立層次網絡的復雜度仍是O（n*m)

現在來分析DFS過程的總復雜度。在每一階段，將DFS分成兩部分分析

（1）修改增廣路的流量并后退的花費
在每一階段，最多增廣m次，每次修改流量的費用為$O(n)$。而一次增廣后在增廣路中后退的費用也為$O(n)$。所以在每一階段中，修改增廣路以及后退的復雜度為$O(m?n)$

（2）DFS遍歷時的前進與后退
在DFS遍歷時，如果當前路徑的最后一個頂點能夠繼續擴展，則一定是沿著第i層的頂點指向第i+1層頂點的邊向匯點前進了一步。因為增廣路經長度最長為n，所以最壞的情況下前進n步就會遇到匯點。在前進的過程中，可能會遇到沒有邊能夠沿著繼續前進的情況，這時將路徑中的最后一個點在層次圖中刪除

注意到每后退一次必定會刪除一個頂點，所以后退的次數最多為n次。在每一階段中，后退的復雜度為$O(n)$

假設在最壞的情況下，所有的點最后均被退了回來，一共共后退了n次，這也就意味著，有n次的前進被“無情”地退了回來，這n次前進操作都沒有起到“尋找增廣路”的作用。除去這n次前進和n次后退，其余的前進都對最后找到增廣路做了貢獻。增廣路最多找到m次。每次最多前進n個點。所以所有前進操作最多為n+m*n次，復雜度為$O(n?m)$

于是得到，在每一階段中，DFS遍歷時前進與后退的花費為$O(m?n)$

綜合以上兩點，一次DFS的復雜度為$O(n?m)$。因此，Dinic算法的總復雜度即$O(m?n?n)$

bfs模板

模板1

bool bfs ( int s, int t ) {memset ( dep, 0, sizeof ( dep ) );dep[s] = 1;while ( !q.empty() )q.pop();q.push( s );while ( ! q.empty() ) {int u = q.front();q.pop();for ( int i = 1;i <= m;i ++ ) {if ( ! dep[i] && edge[u][i].c > edge[u][i].flow ) { dep[i] = dep[u] + 1;q.push( i );}}}return dep[t] != 0; }

模板2

bool bfs ( int s, int t ) {memcpy ( cur, head, sizeof ( head ) );memset ( dep, 0, sizeof ( dep ) );dep[s] = 1;while ( !q.empty() )q.pop();q.push( s );while ( ! q.empty() ) {int u = q.front();q.pop();for ( int i = head[u];i;i = edge[i].next ) {int v = edge[i].to;if ( ! dep[v] && edge[i].flow ) {//有流量就增廣 dep[v] = dep[u] + 1;q.push( v );}}}return dep[t] != 0; }

dfs模板

不帶弧優化模板（最好別用）

int dfs ( int now, int t, int cap ) {if ( now == t ) return cap;int tmp = cap, flow;for ( int i = 1;i <= m && tmp;i ++ ) {if ( dep[i] == dep[now] + 1 && edge[now][i].c > edge[now][i].flow) {flow = dfs ( i, t, min ( tmp, edge[now][i].c - edge[now][i].flow ) );edge[now][i].flow += flow;edge[i][now].flow -= flow;tmp -= flow;}}return cap - tmp; }

帶弧優化模板

int dfs ( int now, int t, int cap ) {//分別是當前點，匯點，當前邊上最小的流量 if ( ! cap || now == t )//終止條件，要么這條路斷了，要么走到了匯點 return cap;int flow = 0;for ( int i = cur[now];i;i = edge[i].next ) {//開始弧優化 cur[now] = i;//記錄一下遍歷到了哪里 int v = edge[i].to;if ( dep[v] == dep[now] + 1 ) {//分層圖，只能往下找一層 int tmp = dfs ( v, t, min ( cap, edge[i].flow ) );if ( ! tmp )//如果tmp=0就意味著找不到增廣路了 continue;flow += tmp;cap -= tmp;edge[i].flow -= tmp;edge[i ^ 1].flow += tmp;//處理反向邊 if ( ! cap ) //沒有殘量就意味著沒有增廣路了 break;}}return flow; }

---

獻上我丑陋的代碼。。。

不帶弧優化版AC代碼

#include <queue> #include <cstdio> #include <cstring> #include <iostream> using namespace std; #define INF 0x7f7f7f7f #define MAXN 205 struct node {int c, flow; }edge[MAXN][MAXN]; queue < int > q; int n, m, cnt = 1; int dep[MAXN];bool bfs ( int s, int t ) {memset ( dep, 0, sizeof ( dep ) );dep[s] = 1;while ( !q.empty() )q.pop();q.push( s );while ( ! q.empty() ) {int u = q.front();q.pop();for ( int i = 1;i <= m;i ++ ) {if ( ! dep[i] && edge[u][i].c > edge[u][i].flow ) { dep[i] = dep[u] + 1;q.push( i );}}}return dep[t] != 0; }int dfs ( int now, int t, int cap ) {if ( now == t ) return cap;int tmp = cap, flow;for ( int i = 1;i <= m && tmp;i ++ ) {if ( dep[i] == dep[now] + 1 && edge[now][i].c > edge[now][i].flow) {flow = dfs ( i, t, min ( tmp, edge[now][i].c - edge[now][i].flow ) );edge[now][i].flow += flow;edge[i][now].flow -= flow;tmp -= flow;}}return cap - tmp; }int dinic ( int s, int t ) {int flow = 0;while ( bfs( s, t ) )flow += dfs ( s, t, INF );return flow; }int main() {scanf ( "%d %d", &n, &m );for ( int i = 1;i <= n;i ++ ) {int si, ei, ci;scanf ( "%d %d %d", &si, &ei, &ci );edge[si][ei].c += ci;}printf ( "%d", dinic ( 1, m ) );return 0; }

帶弧優化AC代碼

#include <queue> #include <cstdio> #include <cstring> #include <iostream> using namespace std; #define INF 0x7f7f7f7f #define MAXN 205 struct node {int next, to, flow; }edge[MAXN << 1]; queue < int > q; int n, m, cnt = 1; int head[MAXN], cur[MAXN], dep[MAXN]; //dep記錄bfs分層圖每個點到源點的距離 void add ( int x, int y, int w ) {cnt ++;edge[cnt].next = head[x];edge[cnt].to = y;edge[cnt].flow = w;head[x] = cnt; }bool bfs ( int s, int t ) {memcpy ( cur, head, sizeof ( head ) );memset ( dep, 0, sizeof ( dep ) );dep[s] = 1;while ( !q.empty() )q.pop();q.push( s );while ( ! q.empty() ) {int u = q.front();q.pop();for ( int i = head[u];i;i = edge[i].next ) {int v = edge[i].to;if ( ! dep[v] && edge[i].flow ) {//有流量就增廣 dep[v] = dep[u] + 1;q.push( v );}}}return dep[t] != 0; }int dfs ( int now, int t, int cap ) {//分別是當前點，匯點，當前邊上最小的流量 if ( ! cap || now == t )//終止條件，要么這條路斷了，要么走到了匯點 return cap;int flow = 0;for ( int i = cur[now];i;i = edge[i].next ) {//開始弧優化 cur[now] = i;//記錄一下遍歷到了哪里 int v = edge[i].to;if ( dep[v] == dep[now] + 1 ) {//分層圖，只能往下找一層 int tmp = dfs ( v, t, min ( cap, edge[i].flow ) );if ( ! tmp )//如果tmp=0就意味著找不到增廣路了 continue;flow += tmp;cap -= tmp;edge[i].flow -= tmp;edge[i ^ 1].flow += tmp;//處理反向邊 if ( ! cap ) //沒有殘量就意味著沒有增廣路了 break;}}return flow; }int dinic ( int s, int t ) {int flow = 0;while ( bfs( s, t ) )flow += dfs ( s, t, INF );return flow; }int main() {scanf ( "%d %d", &n, &m );for ( int i = 1;i <= n;i ++ ) {int si, ei, ci;scanf ( "%d %d %d", &si, &ei, &ci );add ( si, ei, ci );add ( ei, si, 0 );}printf ( "%d", dinic ( 1, m ) );return 0; }

ISAP

算法思想

我們達到如下目標：
能在O(n)時間內判斷每次增廣，如果我們維持“距離標號”且能在O(n)時間內實施增廣.
維持和更新所有距離標號的總時間是O(mn).
總增廣數是O(nm).
結論：總運行時間是O(n^2m)

---

距離標號
距離標號是一個函數：$d:V\to Z+$. 距離標號被稱為是有效，如果它滿足以下:
$d(t)=0$ //匯點的標號為0
$d(i)\le d(j)+1$ 對每個 $(i,j)\in G(f)$
邊 $(i,j)\in G(f)$ 是可進入的，前提是如果 $d(i)=d(j)+1$.

頂點里的數字是各頂點的距離標號。紅色邊是殘留網絡中的可進入弧。可以發現，可進入弧的數量是少于圖中總的邊數的，為找增廣路節約了時間

---

實現
理論上初始距離標號要用反向BFS求得，實踐中可以全部設為0，可以證明：這樣做不改變漸進時間復雜度。
理論上可以寫出許多子程序并迭代實現，但判斷瑣碎，沒有層次，實踐中用遞歸簡單明了
GAP優化：注意到我們在某次增廣后，最大流可能已經求出，因后算法繼續重標號，做了許多無用功。可以發現，距離標號是單調增的。這啟示我們如果標號中存在“間隙”，則圖中不會再有增廣路，于是算法提前終止。
實踐中我們使用數組vd[i]記錄標號為i的頂點個數，若重新標號使得vd中原標號項變為0，則停止算法（出現了斷層） 不必在每次增廣后實時更新圖中的流量，可以讓一條增廣路有多個分叉并統計增廣量，在算法前進與回溯的執行過程中自動更新流量

bfs模板

void bfs () {//初始化bfs，從t到s搜出每個點初始深度 memset ( dep, -1, sizeof ( dep ) );memset ( gap, 0, sizeof ( gap ) );while ( ! q.empty() )q.pop();dep[t] = 0;gap[0] = 1;q.push( t );while ( ! q.empty() ) {int u = q.front();q.pop();for ( int i = head[u];i;i = edge[i].next ) {int v = edge[i].v;if ( dep[v] != -1 )continue;q.push( v );dep[v] = dep[u] + 1;gap[dep[v]] ++;}} }

dfs模板

不帶弧優化

int dfs ( int u, int flow ) {if ( u == t ) {maxflow += flow;return flow;}int used = 0;for ( int i = head[u];i;i = edge[i].next ) {int v = edge[i].v;if ( edge[i].flow && dep[v] + 1 == dep[u] ) {//為什么不是dep[v]==dep[u]+1，請注意我們bfs是從t倒著的，自然而然dep也倒著了 int tmp = dfs ( v, min ( edge[i].flow, flow - used ) );if ( tmp ) {edge[i].flow -= tmp;edge[i ^ 1].flow += tmp;used += tmp;}if ( used == flow )return used;}}//如果已經到此，說明該點u出去的所有點都已經流過了//并且從前面點傳過來的流量flow仍有剩余//則此時要修改該點的dep使得該點與該點出去的所有點分隔開 -- gap[dep[u]];if ( ! gap[dep[u]] )//出現斷層，無法到達匯點t了 dep[s] = n + 1;dep[u] ++;gap[dep[u]] ++; return used; }

帶弧優化

int dfs ( int u, int flow ) {if ( u == t ) {maxflow += flow;return flow;}int used = 0;for ( int i = cur[u];i;i = edge[i].next ) {cur[u] = i;int v = edge[i].v;if ( edge[i].flow && dep[v] + 1 == dep[u] ) {//為什么不是dep[v]==dep[u]+1，請注意我們bfs是從t倒著的，自然而然dep也倒著了 int tmp = dfs ( v, min ( edge[i].flow, flow - used ) );if ( tmp ) {edge[i].flow -= tmp;edge[i ^ 1].flow += tmp;used += tmp;}if ( used == flow )return used;}}//如果已經到此，說明該點u出去的所有點都已經流過了//并且從前面點傳過來的流量flow仍有剩余//則此時要修改該點的dep使得該點與該點出去的所有點分隔開 -- gap[dep[u]];if ( ! gap[dep[u]] )//出現斷層，無法到達匯點t了 dep[s] = n + 1;dep[u] ++;gap[dep[u]] ++; return used; }

不帶弧優化版AC代碼

#include <queue> #include <cstdio> #include <cstring> #include <iostream> using namespace std; #define MAXN 205 #define INF 0x7f7f7f7f struct node {int v, next, flow; }edge[MAXN << 1]; queue < int > q; int maxflow, s, t, n, m, cnt = 1; int dep[MAXN], gap[MAXN], head[MAXN]; //dep[i]表示節點i的深度，gap[i]表示深度為i的點的數量void add ( int x, int y, int w ) {cnt ++;edge[cnt].next = head[x];edge[cnt].flow = w;edge[cnt].v = y;head[x] = cnt; }void bfs () {//初始化bfs，從t到s搜出每個點初始深度 memset ( dep, -1, sizeof ( dep ) );memset ( gap, 0, sizeof ( gap ) );while ( ! q.empty() )q.pop();dep[t] = 0;gap[0] = 1;q.push( t );while ( ! q.empty() ) {int u = q.front();q.pop();for ( int i = head[u];i;i = edge[i].next ) {int v = edge[i].v;if ( dep[v] != -1 )continue;q.push( v );dep[v] = dep[u] + 1;gap[dep[v]] ++;}} } //可以看出ISAP的bfs里面對邊權!=0的條件沒有限制，只需要再后面的dfs里進行判斷即可 int dfs ( int u, int flow ) {if ( u == t ) {maxflow += flow;return flow;}int used = 0;for ( int i = head[u];i;i = edge[i].next ) {int v = edge[i].v;if ( edge[i].flow && dep[v] + 1 == dep[u] ) {//為什么不是dep[v]==dep[u]+1，請注意我們bfs是從t倒著的，自然而然dep也倒著了 int tmp = dfs ( v, min ( edge[i].flow, flow - used ) );if ( tmp ) {edge[i].flow -= tmp;edge[i ^ 1].flow += tmp;used += tmp;}if ( used == flow )return used;}}//如果已經到此，說明該點u出去的所有點都已經流過了//并且從前面點傳過來的流量flow仍有剩余//則此時要修改該點的dep使得該點與該點出去的所有點分隔開 -- gap[dep[u]];if ( ! gap[dep[u]] )//出現斷層，無法到達匯點t了 dep[s] = n + 1;dep[u] ++;gap[dep[u]] ++; return used; }int ISAP () {maxflow = 0;bfs();while ( dep[s] < n )dfs ( s, INF );return maxflow; }int main() {scanf ( "%d %d", &n, &m );for ( int i = 1;i <= n;i ++ ) {int si, ei, ci;scanf ( "%d %d %d", &si, &ei, &ci );add ( si, ei, ci );add ( ei, si, 0 );}s = 1;t = m;printf ( "%d", ISAP() );return 0; }

帶弧優化版AC代碼

如果已經懂了Dinic，其實只要改一點點就好了

#include <queue> #include <cstdio> #include <cstring> #include <iostream> using namespace std; #define MAXN 205 #define INF 0x7f7f7f7f struct node {int v, next, flow; }edge[MAXN << 1]; queue < int > q; int maxflow, s, t, n, m, cnt = 1; int dep[MAXN], gap[MAXN], head[MAXN], cur[MAXN]; //dep[i]表示節點i的深度，gap[i]表示深度為i的點的數量void add ( int x, int y, int w ) {cnt ++;edge[cnt].next = head[x];edge[cnt].flow = w;edge[cnt].v = y;head[x] = cnt; }void bfs () {//初始化bfs，從t到s搜出每個點初始深度 memset ( dep, -1, sizeof ( dep ) );memset ( gap, 0, sizeof ( gap ) );while ( ! q.empty() )q.pop();dep[t] = 0;gap[0] = 1;q.push( t );while ( ! q.empty() ) {int u = q.front();q.pop();for ( int i = head[u];i;i = edge[i].next ) {int v = edge[i].v;if ( dep[v] != -1 )continue;q.push( v );dep[v] = dep[u] + 1;gap[dep[v]] ++;}} } //可以看出ISAP的bfs里面對邊權!=0的條件沒有限制，只需要再后面的dfs里進行判斷即可 int dfs ( int u, int flow ) {if ( u == t ) {maxflow += flow;return flow;}int used = 0;for ( int i = cur[u];i;i = edge[i].next ) {cur[u] = i;int v = edge[i].v;if ( edge[i].flow && dep[v] + 1 == dep[u] ) {//為什么不是dep[v]==dep[u]+1，請注意我們bfs是從t倒著的，自然而然dep也倒著了 int tmp = dfs ( v, min ( edge[i].flow, flow - used ) );if ( tmp ) {edge[i].flow -= tmp;edge[i ^ 1].flow += tmp;used += tmp;}if ( used == flow )return used;}}//如果已經到此，說明該點u出去的所有點都已經流過了//并且從前面點傳過來的流量flow仍有剩余//則此時要修改該點的dep使得該點與該點出去的所有點分隔開 -- gap[dep[u]];if ( ! gap[dep[u]] )//出現斷層，無法到達匯點t了 dep[s] = n + 1;dep[u] ++;gap[dep[u]] ++; return used; }int ISAP () {maxflow = 0;bfs();while ( dep[s] < n ) {memcpy ( cur, head, sizeof ( head ) ); dfs ( s, INF );}return maxflow; }int main() {scanf ( "%d %d", &n, &m );for ( int i = 1;i <= n;i ++ ) {int si, ei, ci;scanf ( "%d %d %d", &si, &ei, &ci );add ( si, ei, ci );add ( ei, si, 0 );}s = 1;t = m;printf ( "%d", ISAP() );return 0; }

肯定有很多問題，歡迎各位Dalao指出

Update(僅模板)

無源匯有上下界可行流

//LOJ 題目同名 #include <queue> #include <cstdio> #include <cstring> using namespace std; #define maxn 205 #define inf 1e9 struct node {int nxt, to, flow; }edge[maxn * maxn]; queue < int > q; int n, m, cnt; int dep[maxn], head[maxn], cur[maxn], d[maxn], minn[maxn * maxn];void addedge( int u, int v, int w ) {edge[cnt].nxt = head[u];edge[cnt].to = v;edge[cnt].flow = w;head[u] = cnt ++;edge[cnt].nxt = head[v];edge[cnt].to = u;edge[cnt].flow = 0;head[v] = cnt ++; }bool bfs( int s, int t ) {memcpy( cur, head, sizeof( head ) );memset( dep, 0, sizeof( dep ) );dep[s] = 1, q.push( s );while( ! q.empty() ) {int u = q.front(); q.pop();for( int i = head[u];~ i;i = edge[i].nxt ) {int v = edge[i].to;if( ! dep[v] && edge[i].flow ) {dep[v] = dep[u] + 1;q.push( v );}}}return dep[t]; }int dfs( int u, int t, int cap ) {if( ! cap || u == t ) return cap;int flow = 0;for( int i = cur[u];~ i;i = edge[i].nxt ) {cur[u] = i;int v = edge[i].to;if( dep[v] == dep[u] + 1 ) {int w = dfs( v, t, min( cap, edge[i].flow ) );if( ! w ) continue;cap -= w;flow += w;edge[i].flow -= w;edge[i ^ 1].flow += w;if( ! cap ) break;}}return flow; }int dinic( int s, int t ) {int ans = 0;while( bfs( s, t ) )ans += dfs( s, t, inf );return ans; }int main() {memset( head, -1, sizeof( head ) );scanf( "%d %d", &n, &m );int s = 0, t = n + 1, sum = 0;for( int i = 0, u, v, low, up;i < m;i ++ ) {scanf( "%d %d %d %d", &u, &v, &low, &up );d[u] -= low;d[v] += low;minn[i] = low;addedge( u, v, up - low );}for( int i = 1;i <= n;i ++ ) {if( d[i] > 0 ) {sum += d[i];addedge( s, i, d[i] );}if( d[i] < 0 )addedge( i, t, -d[i] );}if( sum != dinic( s, t ) ) printf( "NO\n" );else {printf( "YES\n" );for( int i = 0;i < m;i ++ )printf( "%d\n", edge[i << 1 | 1].flow + minn[i] );}return 0; } //無源匯有上下界可行流

有源匯有上下界最大流

//LOJ 題目同名 #include <queue> #include <cstdio> #include <cstring> using namespace std; #define maxn 205 #define inf 1e9 struct node {int nxt, to, flow; }edge[maxn * maxn]; queue < int > q; int cnt; int head[maxn], cur[maxn], dep[maxn], d[maxn];void addedge( int u, int v, int w ) {edge[cnt].nxt = head[u];edge[cnt].to = v;edge[cnt].flow = w;head[u] = cnt ++;edge[cnt].nxt = head[v];edge[cnt].to = u;edge[cnt].flow = 0;head[v] = cnt ++; }bool bfs( int s, int t ) {memcpy( cur, head, sizeof( head ) );memset( dep, 0, sizeof( dep ) );dep[s] = 1, q.push( s );while( ! q.empty() ) {int u = q.front(); q.pop();for( int i = head[u];~ i;i = edge[i].nxt ) {int v = edge[i].to;if( ! dep[v] && edge[i].flow ) {dep[v] = dep[u] + 1;q.push( v );}}}return dep[t]; }int dfs( int u, int t, int cap ) {if( ! cap || u == t ) return cap;int flow = 0;for( int i = cur[u];~ i;i = edge[i].nxt ) {cur[u] = i;int v = edge[i].to;if( dep[v] == dep[u] + 1 ) {int w = dfs( v, t, min( cap, edge[i].flow ) );if( ! w ) continue;cap -= w;flow += w;edge[i].flow -= w;edge[i ^ 1].flow += w;if( ! cap ) break;}}return flow; }int dinic( int s, int t ) {int ans = 0;while( bfs( s, t ) )ans += dfs( s, t, inf );return ans; }int main() {memset( head, -1, sizeof( head ) );int n, m, s, t;scanf( "%d %d %d %d", &n, &m, &s, &t );int ss = 0, tt = n + 1, sum = 0;for( int i = 1, u, v, low, up;i <= m;i ++ ) {scanf( "%d %d %d %d", &u, &v, &low, &up );d[u] -= low, d[v] += low;addedge( u, v, up - low );}for( int i = 1;i <= n;i ++ ) {if( d[i] > 0 ) {sum += d[i];addedge( ss, i, d[i] );}if( d[i] < 0 )addedge( i, tt, -d[i] );}addedge( t, s, inf );if( sum != dinic( ss, tt ) ) return ! printf( "please go home to sleep\n" );else printf( "%d\n", dinic( s, t ) );return 0; } //有源匯有上下界最大流

有源匯有上下界最小流

//LOJ 題目同名 #include <queue> #include <cstdio> #include <cstring> using namespace std; #define int long long #define maxn 50010 #define inf 1e18 #define maxm 400100 struct node {int nxt, to, flow; }edge[maxm]; queue < int > q; int cnt; int head[maxn], cur[maxn], dep[maxn], d[maxn];void addedge( int u, int v, int w ) {edge[cnt].nxt = head[u];edge[cnt].to = v;edge[cnt].flow = w;head[u] = cnt ++;edge[cnt].nxt = head[v];edge[cnt].to = u;edge[cnt].flow = 0;head[v] = cnt ++; }bool bfs( int s, int t ) {memcpy( cur, head, sizeof( head ) );memset( dep, 0, sizeof( dep ) );dep[s] = 1, q.push( s );while( ! q.empty() ) {int u = q.front(); q.pop();for( int i = head[u];~ i;i = edge[i].nxt ) {int v = edge[i].to;if( ! dep[v] && edge[i].flow ) {dep[v] = dep[u] + 1;q.push( v );}}}return dep[t]; }int dfs( int u, int t, int cap ) {if( ! cap || u == t ) return cap;int flow = 0;for( int i = cur[u];~ i;i = edge[i].nxt ) {cur[u] = i;int v = edge[i].to;if( dep[v] == dep[u] + 1 ) {int w = dfs( v, t, min( cap, edge[i].flow ) );if( ! w ) continue;cap -= w;flow += w;edge[i].flow -= w;edge[i ^ 1].flow += w;if( ! cap ) break;}}return flow; }int dinic( int s, int t ) {int ans = 0;while( bfs( s, t ) )ans += dfs( s, t, inf );return ans; }signed main() {memset( head, -1, sizeof( head ) );int n, m, s, t;scanf( "%lld %lld %lld %lld", &n, &m, &s, &t );int ss = 0, tt = n + 1, sum = 0;for( int i = 1, u, v, low, up;i <= m;i ++ ) {scanf( "%lld %lld %lld %lld", &u, &v, &low, &up );d[u] -= low, d[v] += low;addedge( u, v, up - low );}for( int i = 1;i <= n;i ++ ) {if( d[i] > 0 ) {sum += d[i];addedge( ss, i, d[i] );}if( d[i] < 0 ) addedge( i, tt, -d[i] );}int flow = 0;flow += dinic( ss, tt );addedge( t, s, inf );flow += dinic( ss, tt );if( sum != flow ) return ! printf( "please go home to sleep\n" );else printf( "%lld\n", edge[cnt - 1].flow );return 0; } //有源匯有上下界最小流

總結

以上是生活随笔為你收集整理的【网络流】最大流问题（EK算法带模板，Dinic算法带模板及弧优化，ISAP算法带模板及弧优化）上下界网络流的全部內容，希望文章能夠幫你解決所遇到的問題。

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