定義 #
最大流問題是指在一張有向圖，從源點 (source) 到匯流點 (sink) 最多可以傳多少流量。最大流的圖有以下元素 :
- 節點 : 代表交匯點
- 有向邊 : 代表可以傳輸的通道 ( 注意是有向的喔)
- 容量 : 每條邊都有一個容量限制，傳輸的流量不能出過這個限制
- 源點 (s) : 流量的起點
- 匯點 (t) : 流量的終點
舉例 : #
想像一個問題 : 你的一個富有親戚要在家裡蓋尿尿小童，親戚出價 5 億請你接一條水管到親戚家，於是你為了下輩子財富自由接下了案子。下面是你幫親戚規劃的水管管道 :
家 ---管道1(容量5)---> 中繼站 ---管道2(容量3)---> 你的親戚家
在這個例子中，「家」、「中繼站」、「親戚家」是節點 ; 「管道」是有向邊 ; 源點是「家」、匯點是「親戚家」
在上圖中，我們最多可以送多少水給親戚呢 ? 答案顯而易見是 3， 因為管道 2 最多只能承受 3 單位流量，送超過 3 單位就炸了。
也就是說要找送多少流量，就找所有管道容量最小的那個就對了，而這個最小的容量會被稱為「瓶頸」。
增廣路徑 #
像這樣從源點到匯點的路徑我們稱為增廣路徑，像是上面的 「家」 到 「中繼站」 再到 「親戚家」，增廣路徑可能不只一條，它可以有很多條
瓶頸 #
所謂瓶頸指的是那條增廣路徑做多可以送的流量，以上面的例子為例，它的瓶頸會是 3
再一個舉例 : #
s 是你家，t 是親戚家，蓋好水管的隔天親戚告訴你水量太小了，於是你又蓋了另一條水管到親戚家。下面是加蓋後的樣子 :
2
s -----→ a
| |
5| |4
↓ ↓
b -----→ t
3
可以看到
- s -> a -> t 瓶頸是 2 單位流量，因為送了 2 單位流量，所以這條路徑上的容量需要減 2，像這樣 :
0
s -----→ a
| |
5| |2
↓ ↓
b -----→ t
3
- s -> b -> t 瓶頸是 3 單位流量，一樣路徑上的容量減 3
0
s -----→ a
| |
2| |2
↓ ↓
b -----→ t
0
最後你會發現，像這樣把容量減到最後會出現 0 ，0 就代表管道最大能送 0 單位的流量，言下之意就是已經不能送了，並且可以發現走到這一步已經找不到可以送流量的增廣路徑，所以是時候結算了
最後結算，最終的最大流會是 2 + 3 = 5 單位
反向邊 #
才剛幫你的富有親戚新建完水管，你從大○公園的草地上醒來，清晨的陽光溫暖地灑落在你的臉上，此時電話鈴聲突然響起，你一臉不情願地接起電話 :「小○阿，我覺的水的流量還是太少了，我在出價 3 億幫我接更多的水管」聽到這突如其然的消息讓你興奮不已，原本還睡臉惺忪的你現在彷彿吸了大○一樣，臉上露出了誇張的笑容，在周圍「這孩子有○吧」的視線下離開了公園。下面是你加蓋後的管線圖 :
(請原諒我用這種奇怪的方式畫圖)
s
10 ／＼ 10
↙ 1 ↘
a ———→ b
10 ＼ ∕ 10
↘ ↙
t
根據前面的經驗，這張圖的最大流應該是 s -> a -> t 的 10 和 s -> b -> t 的 10 加起來，所以是 20。
但是但是，事情的發展往往不如意，找增廣路徑的方法是用 DFS 或 BFS 嗎，問題就在這裡，假設用 DFS 好了，DFS 不一定會找到 s -> a -> t 或 s -> b -> t ，它有可能會找到
s -> a -> b -> t，那走這一條會發生甚麼事 ? 它會讓最大流 +1 同時使圖變成這樣 :
s
9 ／＼ 10
↙ 0 ↘
a ———→ b
10 ＼ ／ 9
↘ ↙
t
這樣推算下去，最大流會是 1 + 9 + 9 = 19 ，而正確的結果應該是 20，為了解決這個問題人們提出了「反向邊」。
像 a -> b 這樣的叫做「正向邊」，那反向邊就是反過來變成 b -> a ，一開始反向邊預設都是 0 ，但當增廣路徑被決定時，路徑上的「正向邊」會減去瓶頸，「反向邊」則會加上瓶頸，那這個「反向邊」為什麼可以解決問題呢 ? 我們來一步一步模擬它 !
現在我們分成正向邊和反向邊一起來看
正向邊
s
10 ／＼ 10
↙ 1 ↘
a ———→ b
10 ＼ ／ 10
↘ ↙
t
反向邊
s
0 ↗ ↖ 0
／ 0 ＼
a ←——- b
0 ↖ ↗ 0
＼ ／
t
如果不幸地走了 s -> a -> b -> t 這條 ，你會發現所有路徑上的正向邊都減了 1，而返向邊都加了 1 ，此時最大流 = 1
正向邊
s
9 ／＼ 10
↙ 0 ↘
a ———→ b
10 ＼ ／ 9
↘ ↙
t
反向邊
s
1 ↗ ↖ 0
／ 1 ＼
a ←——- b
0 ↖ ↗ 1
＼ ∕
t
假設接下來走了s -> a -> t 和 s -> b -> t ，最大流 = 1 + 9 + 9
正向邊
s
0 ／＼ 1
↙ 0 ↘
a ———→ b
1 ＼ ／ 0
↘ ↙
t
反向邊
s
10 ↗ ↖ 9
／ 1 ＼
a ←——- b
9 ↖ ↗ 10
＼ ／
t
如果只看正向邊，會發現沒有路可以走了，因為所有增廣路徑的瓶頸都是 0，但是 !! 如果把反向邊也考慮進去，你將發現出現了 s -> b -> a -> t 這條路，關鍵在於 b -> a 這條路，最一剛開始的 b -> a 因為是 0 所以不能走 ，但後來因為走了 a -> b 這條路，導致反向邊加上了消耗的流量，讓現在變成可以走的狀況，所以最後的最大流會是 : 1 + 9 + 9 + 1 = 20 ，看 ! 原本不使用反向邊是 19 ，加了反向邊後就自動修正成了 20
總結來說，反向邊是一個很神奇的東西，它可以補上少加上的流量，因此很神奇吧 ! 不知道這個方法當初是怎麼想出來的，不過不知道為什麼反向邊有這樣的效果沒關係 ! 只要知道這樣做有效果就好了~
Ford-Fulkerson 核心思想 #
Ford-Fulkerson 的核心思想就是 :
- 找一條增廣路徑 (可以使用 DFS or BFS)
- 找出那條增廣路徑的瓶頸，例如 :
- s -> A 最多 5
- A -> B 最多 3
- B -> t 最多 10 瓶頸 = min(5 , 3 , 10) = 3
- 把這些容量加進去，也就是
- 路徑上的所有正向邊：流量 - 3
- 路徑上的所有反向邊：流量 + 3
- 跳到第 1 步，直到找不到增廣路徑
程式 #
( 程式參考自 claude )
假設輸入格式是這樣子 :
輸入格式:
n m s t
u1 v1 cap1
u2 v2 cap2
- 節點數 \(n\)
- 邊數 \(m\)
- 源點 \(s\)
- 匯點 \(t\)
- 起點 \(u_i\)
- 終點 \(v_i\)
- 容量 \(cap_i\)
以防你不知道，i 是 1、2、3、4 …. 一直到正無限的意思
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 505;
const int INF = 1e9;
struct Edge {
int to, cap, rev; // 終點、容量、反向邊編號
};
vector<Edge> graph[MAXN];
bool visited[MAXN];
int n; // 節點數
// 加邊:u->v 容量 cap
void addEdge(int u, int v, int cap) {
graph[u].push_back({v, cap, (int)graph[v].size()});
graph[v].push_back({u, 0, (int)graph[u].size() - 1}); // 反向邊容量0
}
// DFS 找增廣路徑並回傳能推送的流量
int dfs(int v, int t, int f) {
if (v == t) return f; // 到達匯點，回傳這條路徑的瓶頸流量
visited[v] = true; // 標記走過，避免死迴圈
for (auto &e : graph[v]) {
if (!visited[e.to] && e.cap > 0) { // 沒走過且還有殘留容量
// 遞迴往下找，並隨時更新整條路徑的「最小瓶頸容量」
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) { // 成功找到路徑跑到終點了！
e.cap -= d; // 正向邊減少
graph[e.to][e.rev].cap += d; // 反向邊增加
return d;
}
}
}
return 0;
}
// Ford-Fulkerson 主函數
int maxFlow(int s, int t) {
int flow = 0;
while (true) {
memset(visited, false, sizeof(visited)); // 每次找路徑前都要重置拜訪紀錄
int f = dfs(s, t, INF); // 初始流量給無限大 (INF)
if (f == 0) break; // 找不到增廣路徑
flow += f; // 累加找到的流量
}
return flow;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m, s, t;
cin >> n >> m >> s >> t; // 節點數、邊數、源點、匯點
for (int i = 0; i < m; i++) {
int u, v, cap;
cin >> u >> v >> cap;
addEdge(u, v, cap);
}
cout << maxFlow(s, t) << endl;
return 0;
}
あれ ? graph 不是一維陣列嗎 ? #
在程式中可以發現 vector<Edge> graph[MAXN] 這個「看起來」是 1 維的 vector 陣列，但是在做 dfs 找增廣路徑時，卻使用了 graph[e.to][e.rev].cap += d ，這樣做不會編譯失敗嗎 ?
我一開始以為 vector<Edge> graph[MAXN] 的意思是指 「有 MAXN 個格子，每一個格子都是用來裝 Edge 資料型態的空間 」，但其實不是，這段程式和 vector<vector<Edge>> graph(MAXN) 是類似的意思，雖然運作上有點不同，但都是陣列裝陣列的概念，不要把它誤會成 vector<Edge> graph 喔，vector<Edge> graph 才是一維陣列的寫法。
所以在 addEdge() 裡面才可以寫成 graph[u].push_back({v, cap, (int)graph[v].size()}) 因為 graph[u] 本身就代表 vector 陣列，因此可以使用 .push_back()。
最後還有一個重點，不要忘記一個節點可以連好多個有向邊出去，這也是為什麼需要使用 .push_back() 這樣的寫法，如果忘記這點在理解程式上會有困難 ( 別問我怎麼知道的 )
rev #
注意看到程式中有一個叫 rev 的變數，這個變數是做什麼的 ? 它是用來記錄反向邊在陣列中的位置，舉一個例子:
addEdge (0,1,500)
addEdge (0,2,300)
它的意思是節點 00 到節點 01 有連接並且水管容量是 500 ; 節點 00 到節點 02 有連接並且水管容量是 300 ，知道一個節點可以射好多個有向邊出去是重要的 ! 來看一下這樣子程式會做什麼 ?
void addEdge(int u, int v, int cap) {
graph[u].push_back({v, cap, (int)graph[v].size()});
graph[v].push_back({u, 0, (int)graph[u].size() - 1}); // 反向邊容量0
}
- 建立正向邊 (0 \(\to\) 1)，它的反向邊在 1 號節點那一格的第 0 個位置
- 建立反向邊 (1 \(\to\) 0)，它的正向邊在 0 號節點那一格的第 0 個位置
graph[0][0] 會是 {1,500,0}
graph[1][0] 會是 {0,0,0}
- 建立正向邊 (0 \(\to\) 2)，它的反向邊在 2 號節點那一格的第 1 個位置
- 建立反向邊 (2 \(\to\) 0)，它的正向邊在 0 號節點那一格的第 1 個位置
graph[0][1] 會是 {2,300,1}
graph[1][1] 會是 {0,0,1}
然後你看後面的這段反向邊加上流量的程式 :
graph[e.to][e.rev].cap += d;
應該就能明白為什麼要這樣設計了
為什麼一個是 .size() 一個是 .size()-1 呢 ? 這和陣列從 0 開始算有關，就這樣想 : 因為 graph[v] 是後面才 .push_back() 東西進去，所以它的 .size() 也就是大小剛好是「下一個」的 index，而 graph[u] 因為已經 .push_back() 東西進去了，所以需要減 1 才是正確的位置 !
memset 是什麼 ?
#
memset 是 C++ cstring 函式庫裡面的一個玩意兒，以程式中的這段為例 :
memset(visited, false, sizeof(visited));
意思是把 visited 這個陣列的值全部設成 fale，值得一提的是它的第 3 參數也就是 sizeof(visited)) 這部分，使用的單位是 byte ，不過最基本的用法就是寫成 sizeof(陣列)。
其它的 #
這些是啥 ?
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
是一些程式競賽會用到的「咒語」，可以加速 cin 和 cout ，但如果有用 ios_base::sync_with_stdio(false) 就不能把 cin、cout 和 scanf、printf 混著用，不然會出狀況
我也不太清楚他們倆具體是怎麼運作的，只要知道可以加速輸入輸出就好了 !
