基本概念

流網絡

對于一個有向圖, 抽象成水管里的水的模型, 每根管子有容量限制, 計為$G=(V,E)$, 首先不考慮反向邊

對于任意無向圖, 都可以將反向邊轉化為上述形式

如果一條邊不存在, 定義為容量為$0$, 形式上來說就是$c(u,v)=0$

可行流

對于每一個流網絡考慮一個可行流$f$, 指定每條邊的流量, 需要滿足兩個條件

• 容量限制 $0\le f(u,v)\le c(u,v)$
• 流量守恒, 對于每個點來說, 流進去多少, 流出來多少, 形式化來說

$$\sum _{(v,u)}f(v,u)=\sum _{(u,v)}f(u,v)$$
對于一個可行流, 從源點流向匯點的流量定義為$|f|$, 每秒從源點流出的流量, 或者流入匯點的流量, 每秒凈往外流出的流量

$$|f|=\sum _{(s,v)}f(s,v)?\sum _{(v,s)}f(v,s)$$

最大流指的是流量值最大的可行流

殘存網絡

殘存網絡是對于流網絡某一個可行流

對于某個可行流$f_1$, 殘存網絡$G_{f_1}$
殘存網絡的點集與原圖完全一致$V_f=V$, 但是邊集不僅包含原圖的邊還包含原圖的反向邊$E_f=E+E^{\prime }$

殘存網絡也是流網絡

對于殘存網絡的容量記為$c^{\prime }(u,v)$

• 對于原圖的邊, 那么$c^{\prime }(u,v)=c(u,v)?f(u,v)$
• 對于原圖的反向邊, $c^{\prime }(u,v)=f(v,u)$

對于任意一個可行流$f$, 都可以求出殘存網絡$G_f$

記殘存網絡的可行流$f^{\prime }$, $f+f^{\prime }$也是原來流網絡$G$的一個可行流

新的流的流量值等于兩個流的流量值之和 $|f+f^{\prime }|=|f|+|f^{\prime }|$, 流量相加等同于每條邊相加

為什么新的流是原流網絡$G$的可行流?

• 是否滿足容量限制
• 是否滿足流量守恒

增廣路徑

在殘存網絡中, 從源點出發沿著**容量大于$0$**的點走如果能走到匯點, 那么這一條路徑就是增廣路徑

上述紅色路徑就是增廣路徑, 增廣路徑一定是一個可行流, 流量大于$0$
如果$G_f$總不存在增廣路徑, 斷言$f$是原來流網絡的最大流

割

將點集$V$分為兩個集合$S,T$, 滿足以下條件

• $s\in S$, $t\in T$
• $S\cup T=V$, $S\cap T=?$

上述就是割的形式化描述

割的容量

所有從$S$指向$T$的邊, 被稱為割的容量, 容量不考慮回來的邊

$$c(S,T)=\sum _{u\in S,v\in T}c(u,v)$$

割的流量

所有從$S$留到$T$的流量減去從$T$流向$S$的流量, 也就是凈流量

$$f(S,T)=\sum _{u\in S,v\in T}f(u,v)?\sum _{u\in T,v\in S}f(u,v)$$

對于一個流網絡來說, 如果流網絡確定, 那么割的容量確定, 但是因為一個流網絡存在多個可行流, 因此割的流量是取決于每個可行流的流量的

性質1: 最小割指的是最小割的容量, 對于任意一個割以及任意一個可行流, 割的流量小于等于割的容量, 形式化來說$f(S,T)\le c(S,T)$, 證明過程如下

性質2: 對于流網絡的任意一個割和任意一個可行流都有 $f(S,T)=|f|$

根據性質1和性質2推出$|f|=f(S,T)\le c(S,T)$, 也就推出$|f|\le c(S,T)$, 也就是最大流小于等于最小割

最大流最小割定理

對于某個流網絡$G=(V,E)$, 以下三個結論相互等價

1. 可行流$f$是最大流
2. $f$的殘存網絡中不存在增廣路徑
3. 存在割$[S,T]$, 使得$c(S,T)=|f|$

證明如下

$1$推$2$
反證法, 存在增廣路徑, 由上述增廣路徑定理可知, 當前可行流不是最大流

$3$推$1$
因為$|f|\le c(S,T)$, 對于結論$3$, 存在一個割使得$|f|=c(S,T)$, 證明$f$是否是最大流
$最大流\ge |f|$, 又因為$|f|=c(S,T)\ge 最大流$, 因此$f$是最大流

由結論$3$得知, $最小割\le c(S,T)=|f|\le 最大流$, 也就有最小割小于等于最大流, 上述性質2可知, 最大流小于等于最小割, 因此最大流等于最小割

$2$推$3$
如果當前殘存網絡不存在增廣路徑, 能否構造出一個割, 使得$c(S,T)=|f|$
構造一個合法的割
點集$S$是在$G_f$中$s$沿著容量大于$0$的邊走, 走到的所有點, 因為不存在增廣路徑, 因此$s$走不到$t$
點集$T$是$V?S$
借助的$G_f$構造的是原網絡$G$里的割

判斷當前割的容量是否等于$|f|$

構造的割的性質如下

1. $f(x,y)=c(x,y)$
2. $f(a,b)=0$

對于性質1, 如果$f(x,y)<c(x,y)$, 那么在殘存網絡中仍然會有$x$連到$y$的邊, 也就$x$能遍歷到, $y\in S$, 與我們構造的矛盾
對于性質2, 如果$f(a,b)>0$, 那么在殘存網絡中也是能遍歷到, $a\in S$, 與我們構造的矛盾

$$|f|=\sum _{u\in S,v\in T}f(u,v)?\sum _{u\in T,v\in S}f(u,v)$$

因為沒有反向邊, 并且每個邊的流量等于邊的容量, 因此

$$|f|=\sum _{u\in S,v\in T}c(u,v)=c(S,T)$$

最大流最小割定理證畢

最大流算法實現

$Ford–Fulkerson$方法

求最大流的貪心方法, 維護殘存網絡, 不斷的在殘存網絡中尋找增廣路徑, 將當前流變為$f+f^{\prime }$, 然后在新的流的殘存網絡中繼續尋找增廣路徑, 將當前殘存網絡$G_f$變為$G_{f+f^{\prime }}$

上圖是殘存網絡中更新的過程, $k$是路徑的流量, 也就是所有邊容量的最小值, 然后更新所有邊的容量

$Edmonds–Karp$算法求最大流

時間復雜度$O(n{m}^2)$

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1010, M = 20010, INF = 0x3f3f3f3f;int n, m, s_node, t_node;
int head[N], edge_end[M], next_edge[M], w[M], edge_index;
int q[N], pre[N], min_val[N];
bool vis[N];void add(int ver1, int ver2, int val) {edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], w[edge_index] = val, head[ver1] = edge_index++;
}bool bfs() {memset(vis, false, sizeof vis);int h = 0, t = -1;q[++t] = s_node;vis[s_node] = true;min_val[s_node] = INF;while (h <= t) {int u = q[h++];for (int i = head[u]; ~i; i = next_edge[i]) {int ver = edge_end[i];if (!vis[ver] && w[i]) {vis[ver] = true;min_val[ver] = min(min_val[u], w[i]);pre[ver] = i;if (ver == t_node) return true;q[++t] = ver;}}}return false;
}int edmonds_karp() {int res = 0;while (bfs()) {int val = min_val[t_node];res += val;for (int i = t_node; i != s_node; i = edge_end[pre[i] ^ 1]) {w[pre[i]] -= val;w[pre[i] ^ 1] += val;}}return res;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m >> s_node >> t_node;while (m--) {int u, v, w;cin >> u >> v >> w;add(u, v, w);add(v, u, 0);}int res = edmonds_karp();cout << res << "\n";return 0;
}

$Dinic$算法求最大流

將所有能夠增廣的路徑全部計算, 因為可能有環, 因此使用分層圖優化, 路徑只能從前一層走到后一層
分層圖 + 當前弧優化
時間復雜度$O(n^{2}m)$

從起點到終點, 可以流$limit$的流量, 搜索從當前點開始到終點能流的流量

假設在搜索到終點后流量$f_i<limit$, 說明$f_i$一定會滿流, 那么在下一次搜索的時候不需要搜索該邊

而是從下一條邊開始搜, 代碼表示為$curr[u]=i$

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 10010, M = 200010, INF = 0x3f3f3f3f;int n, m, s_node, e_node;
int head[N], edge_end[M], next_edge[M], w[M], edge_index;
int q[N], layer[N], curr[N];void add(int ver1, int ver2, int val) {edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], w[edge_index] = val, head[ver1] = edge_index++;
}bool bfs() {memset(layer, -1, sizeof layer);int h = 0, t = -1;q[++t] = s_node;layer[s_node] = 0;curr[s_node] = head[s_node];while (h <= t) {int u = q[h++];for (int i = head[u]; ~i; i = next_edge[i]) {int ver = edge_end[i];if (layer[ver] == -1 && w[i]) {layer[ver] = layer[u] + 1;curr[ver] = head[ver];if (ver == e_node) return true;q[++t] = ver;}}}return false;
}int dfs(int u, int limit) {if (u == e_node) return limit;// 從當前點向后流的流量int flow = 0;for (int i = curr[u]; ~i && flow < limit; i = next_edge[i]) {int ver = edge_end[i];// i前面的邊都用完了, 當前弧更新為icurr[u] = i;if (layer[ver] == layer[u] + 1 && w[i]) {int val = dfs(ver, min(w[i], limit - flow));if (!val) layer[ver] = -1;w[i] -= val;w[i ^ 1] += val;flow += val;}}return flow;
}int dinic() {int res = 0, flow;while (bfs()) {// 搜索增廣路徑并且累計全部的流量while ((flow = dfs(s_node, INF))) {res += flow;}}return res;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m >> s_node >> e_node;while (m--) {int u, v, w;cin >> u >> v >> w;add(u, v, w);add(v, u, 0);}int res = dinic();cout << res << "\n";return 0;
}