IThome 2024 鐵人賽 一直刷 CTF - Day1
最大流 & 最小割 (Max-Flow & Min-Cut)
前言
一個由多個站點連接而成的網絡裡,每對站點之間都有一定的數據傳輸限制 (單向)。現在你需要計算從網絡的入口(
\(s\) )到出口( \(t\)
)之間,數據可以同時傳輸的最大速度是多少。
如下圖,從 \(s\) 到 \(t\)
的最大傳輸速度為 2,最大速度會被路徑上最大傳輸流量所限制,因爲從 \(s\) 到 \(t\) 勢必通過路線 \(v1\rightarrow v2\)
,故這張圖的最大流量為 2。
flowchart LR
s --10--> v1 --2--> v3 --13--> v4 --11--> t
而下面這個圖的最大流量為 19,下文提供一種可能的傳輸方式:
flowchart LR
s --10--> v1
s --17--> v2
v1 --7--> v3 --11--> t
v2 --9--> v4 --16--> t
v1 --6--> v4
- 傳輸 7: \(s\rightarrow v1\rightarrow v3\rightarrow t\)
- 傳輸 3: \(s\rightarrow v1 \rightarrow v4 \rightarrow t\) (因為 \(s\rightarrow v1\) 最多只能傳輸 10 因此在前一次傳輸 7 之後,接下來就只能傳輸 3 了)
- 傳輸 9: \(s \rightarrow v2 \rightarrow v4 \rightarrow t\)
- 7+3+9=19
上述這樣的圖叫做 Network
Flow (網路流),在這樣的圖上尋找這種最大流
的想法還可以運用在最小割
(後文會再解釋)、最多不重複路徑
、二分圖最大匹配
、二分圖最小頂點覆蓋
等圖論問題。