# 擴充路徑演算法 Augmenting Path Algorithm
擴充路徑演算法是一個找二分圖匹配的算法，可以無向的 $X, Y$- 二分圖進行 $X$ 與 $Y$ 的匹配，同時也可以用演算法的方式，將 [Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem)證出來
有些人會將此演算法與匈牙利演算法搞混，所以特別需要說明一下，匈牙利演算法是使用矩陣尋找二分圖最大權完美匹配，而擴充路徑演算法則是使用單純的連邊關係，反覆迭代跑 DFS 或 BFS 來完成二分圖最大基數匹配。兩者的時間複雜度也有差異，匈牙利演算法的時間為 $O(n^3)$，而擴充路徑演算法則是 $O(mn)$
似乎也有人將擴充路徑演算法稱作 [Kuhn's algorithm](https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html)
如果想完全理解本篇內容，可以閱讀前面的章節[匹配與霍爾定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem)、[Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem)
## 擴充路徑演算法 Augmenting Path Algorithm
擴充路徑演算法顧名思義需要使用[擴充路徑 (又稱為增廣路徑)](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem#%E6%93%B4%E5%85%85%E8%B7%AF%E5%BE%91-Augmenting-Path) 的性質，也就是透過其定義中的「兩終點都是未匹配點」來尋找新的匹配
### 輸入
一張 $X, Y$-二分圖 $G$、一個在 $G$ 中的匹配 $M$，在 $X$ 中的未飽和點集 $U$
### 想法
令 $S\subseteq X$ 與 $T\subseteq Y$ 為已經碰到的節點集。我們可以從 $U$ 探索一條 $M$-alternating path，並把 $S$ 中有探索過的節點打上記號。當碰到一個節點時，紀錄此節點是被誰碰到的
### 演算法
初始化: $S=U$、$T=\emptyset$
迭代: 從 $U$ 探索一條 $M$-alternating path
- 若 $S$ 沒有未標記的節點，則 $T\cup(X-S)$ 為最小點覆蓋，停止迭代
- 若 $S$ 有未標記的節點，則挑選一個未標記的節點 $x\in S$ 來探索，在探索所有 $x$ 的鄰居後，標記 $x$ 並繼續迭代。在探索時，我們考慮 $y\in N(x)$ 且 $xy\notin M$:
- 若 $y$ 是未飽和的 (saturated 即未被配對)，則停止並回傳一條從 $U$ 到 $y$ 的擴充路徑
- 否則，$y$ 就是已經跟某 $w\in X$ 配對過的節點。在此情況下，將 $y$ 加進 $T$、$w$ 加進 $S$
### 舉例說明
這是我們原本的 $X,Y$-二分圖。其中綠色邊為匹配 $M$ 中的邊、$S$ 初始為 $U$，即 $X$ 中的未配對點集，且 $S$ 中的節點皆未標記
<center>
</center>
$~$
我們可以挑 $S$ 中最左邊的未標記節點來探索，發現他的鄰居是一個飽和的點，所以我們可以將鄰居加入 $T$，其匹配點加入 $S$
<center>
</center>
$~$
接下來我們可以再挑一個 $S$ 中未標記的節點，將其鄰居探訪之後發現可以產生一條新的擴充路徑，因兩終點皆未匹配。我們將其視為新的<font color="green">匹配</font>並停止迭代
<center>
</center>
$~$
## 反覆執行擴充路徑演算法
### 想法
從上面的例子可以發現，我們可以反覆尋找一條新的擴充路徑，直到 $|M|=|T\cup(X-S)|$ 時，也就是匹配數等於最小點覆蓋數的時候，就可以找到最大匹配
### 舉例說明
以下例子，我們延續上面的 $X,Y$-二分圖。其中綠色邊為匹配 $M$ 中的邊、$S$ 初始為 $U$，即 $X$ 中的未配對點集，且 $S$ 中的節點皆未標記
<center>
</center>
$~$
我們可以挑 $S$ 中最左邊的未標記節點來探索，發現他的鄰居是一個飽和的點，所以我們可以將鄰居加入 $T$，其匹配點加入 $S$
<center>
</center>
$~$
接下來我們可以再挑一個 $S$ 中最右邊未標記的節點，並拜訪其還沒在 $T$ 中的鄰居，再沿著匹配邊，又發現新的未標記點，將鄰居與其匹配點分別加入 $T$ 與 $S$。因為鄰居探訪完了，所以打上標記
<center>
</center>
接下來我們可以挑右邊數來第一與第三個 $S$ 中的節點，發現他們的鄰居都已經在 $T$ 裡面了，所以我們沒什麼好做的，就把他們打上標記
<center>
</center>
$~$
最後只剩從左數來第二個節點上未打上標記，因此我們先去探訪他的鄰居。由於發現他的其中一個鄰居是未飽和的，我們可以找到一條<font color="red">擴充路徑</font>，並結束迭代。根據 [Berge 定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem#Berge-%E5%AE%9A%E7%90%8612)，此擴充路徑中，我們可以找到更大的匹配
<center>
</center>
<p class="text-center">
↓
<br>
↓
<br>
↓
</p>
<center>
</center>
$~$
最後，由於 $X$ 中仍有一節點尚未飽和，我們再迭代一次，但是因為篇幅的緣故，跳個步驟，詳細過程可以自己畫畫看。最終，圖會長這樣
<center>
</center>
$~$
可以發現，$|M|=|T\cup(X-S)|$，且 $T\cup(X-S)$ 是最小點覆蓋
### 定理 : 正確性
#### 命題
對二分圖重複執行擴充路徑演算法，最終會產生相同大小的匹配與點覆蓋
#### 證明
由於擴充路徑演算法本來就會產生擴充路徑，我們只需要證明他會產生一組大小為 $|M|$ 的點覆蓋 $Q=T\cup(X-S)$ 即可
一條從 $U$ 進入 $X$ 的 $M$-alternating path 只會在 $M$ 中的邊上，因此所有 $S-U$ 的節點 $x$ 只會通過 $M$ 來配對 $T$，且並沒有任何一條 $M$ 中的節點會從 $S$ 到 $Y - T$。此外，也不會有任何 $M$ 外的邊是這種情況。當一條路徑到達 $x\in S$ 時，可以繼續沿著不是 $M$ 的邊走，並把鄰居都加入 $T$ 中。因演算法在停止之前會標記所有 $S$ 的節點，所有從 $S$ 出發的點都會到達 $T$
此演算法只會把飽和的節點放進 $T$，也就是每個 $y\in T$ 都會通過 $M$ 配對到 $S$ 中的節點。由於 $U\subseteq S$ 且每個 $X-S$ 中的節點都是飽和的，$M$ 中與 $X-S$ 關聯的邊沒有辦法碰到 $T$，所以他們與使 $T$ 飽和的邊是不同的邊。藉由前面的推理，在演算法中我們可以發現 $M$ 有最少 $|T|+|X-S|$ 條邊。因沒有辦法產生大於此匹配的點覆蓋，因此我們得到 $|M|=|T|+|X-S|=|Q|$
### 時間複雜度
每次迭代都要找一個所有的點
而匹配數量有可能會等於邊數
因此總時間複雜度 : $O(nm)$
## 使用 DFS 實作擴充路徑演算法
此方法簡而言之就是用 DFS 或 BFS 做出反覆尋找擴充路徑的過程。其實這不難理解，因為原本的算法我們需要一直停下迭代步驟，然後再重新來過，這會造成大量的時間損失
詳細步驟文字敘述會看起來很燥，看程式碼會比較好懂，在此就不多加贅述
### 程式實作
這邊使用鄰接矩陣實作，空間複雜度非常差，如果想省空間的話建議還是使用鄰接串列
```cpp
bool vis[MXN], adj[MXN][MXN];
int mat[MXN]; // 其中 adj 為鄰接表, mat 為紀錄這個點與誰匹配
int n, p, ans; // n: X 集合數量, p: Y 集合數量, ans: 紀錄答案
bool tag[MXN]; // 紀錄是否被配對過
bool dfs(int u) { // 1-based
for (int i = n + 1; i <= n + p; i++) {
if (adj[u][i] && !vis[i]) { // 有連通且未拜訪
vis[i] = 1; // 紀錄是否走過
if (mat[i] == -1 || dfs(mat[i])) {
mat[i] = u, tag[u] = true; // 紀錄匹配
return true; // 反轉匹配邊以及未匹配邊的狀態
}
}
}
return false;
}
void solve() {
for (int i = 1; i <= n + p; i++)
mat[i] = -1;
ans = 0;
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis)); // 記得每次使用需清空 vis
if (dfs(i))
ans++;
}
}
```
這個演算法優秀的地方在於，他只利用 DFS 本身的機制，寫起來比其他的方法 (e.g. max-flow 的演算法) 更有彈性，模板更容易修改。甚至在有些題目中，我們只需要建左集合的點，右集合不需要真的建出來，可以省掉一些空間，亦或是當我們不知道右集合實際會是多大時，可以直接砸 map 來優化避免不必要的建邊
### 時間複雜度
總時間複雜度 : $O(mn)$
## 例題說明
來源: [Zerojudge i179. 防守城堡 (Defense)](https://zerojudge.tw/ShowProblem?problemid=i179)
### 題目
題目是說在一個 $M\times N$ 方格棋盤上，可以在下方與右方的邊界放置砲台，也可以在每格放置十字形的陷阱，十字形的陷阱會摧毀整個橫縱座標的所有砲台。小東會放置 $T$ 個十字陷阱，且希望一個陷阱最多摧毀一個砲台就好，問最多可以放幾台砲台
### 限制
- $1\leq m, n \leq 500$
- $0\leq T \leq mn$
- $0\leq R < M$
- $0\leq C < N$
- $R,C$ 是座標
### 題解
可以視每個十字陷阱都會匹配下與右兩個位置
如下圖，將能放置砲台的位置編號，並把陷阱當成邊。我們就可以輕易發現，此問題可以轉化成兩砲台匹配的問題
<center>
 
</center>
匹配完之後再加上未匹配的砲台就會是答案
### 程式實作
```cpp
/* 以上略 */
int main() {
int h, w, t, x, y;
cin >> h >> w >> t;
while (t--) {
cin >> x >> y;
adj[1 + x][1 + y + h] = true; // 加入鄰接矩陣
}
n = h, p = w;
solve(); // 跑二分圖匹配
memset(vis, 0, sizeof(vis)); // 這邊把 vis 重複利用
for (int i = n + 1; i <= n + p; i++) {
if (mat[i] != -1) // 如果沒被匹配就標記
vis[S[i]] = vis[i] = true;
}
for (int i = 1; i <= h + w; i++) // 加上沒被匹配的點
ans += !vis[i];
cout << ans << '\n'; // 輸出答案
return 0;
}
```
## 備註
- 擴充路徑演算法 (Kuhn's algorithm) 算是匈牙利演算法 (Kuhn-Munkres algorithm) 的子程式
- 此算法不是尋找二分圖匹配的最佳解。其實，Hopcroft-Karp 演算法有更好的複雜度 $O(m\sqrt{n})$，但是礙於他比較難懂，且實作很複雜，我也不會那個東西
- 其實也可以使用網路流量建模來找出最大二分圖匹配。在 Dinic 演算法中跑二分圖匹配的時間複雜度是 $O(m\sqrt{n})$，因此 Hopcroft-Karp 演算法通常不會拿來打競程，因 Dinic 演算法更實用
- 透過 [Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem)，我們可以將二分圖最小點覆蓋問題、二分圖最大獨立集問題與二分圖最小邊覆蓋問題都轉化成二分圖最大 (基數) 匹配問題等等。這些問題的轉換在[這篇](https://hackmd.io/@ShanC/bipartite-and-flow)有詳細說明
## 題目練習
[CSES School Dance](https://cses.fi/problemset/task/1696/) (裸題)
[Zerojudge h901. 電橘子與電耗子](https://zerojudge.tw/ShowProblem?problemid=h901) (二分搜 + 配對)
[Zerojudge c484. kevin 的西洋棋](https://zerojudge.tw/ShowProblem?problemid=c484) (奇偶建圖)
[Zerojudge d739. 最少路径覆盖](https://zerojudge.tw/ShowProblem?problemid=d739) (把每個點拆成出點/入點，再考慮連邊與匹配要怎麼轉換)
[Zerojudge c455. 4. 警力配置](https://zerojudge.tw/ShowProblem?problemid=c455) ([Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem)裸題，不知道為什麼 $O(nm)$ 可以過，可能沒跑滿吧)
[SWERC2023 Problem B. Supporting everyone](https://codeforces.com/gym/104945/problem/B) (簡單的)
[2020 TOPC Problem G.Garden](https://drive.google.com/file/d/1l-cx_4R9tsaELkxJqbMP8xBEnj8SFSyB/view)
[OnlineJudge 259 - Software Allocation](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=195) (想辦法轉成二分圖匹配吧加油)
[OnlineJudge 10080 - Gopher II](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1021) (跑的到就建邊，記得多比測資)
[SWERC2014 Problem D.Book Club](https://codeforces.com/gym/100783/attachments) (檢查是否有完美匹配)
[Codeforces Gym 101201 G.Maximum Islands](https://codeforces.com/gym/101201/attachments) (連通塊 + 二分圖最大獨立集)
[Codeforces Round 668 (Div. 1) Problem E. Bricks](https://codeforces.com/problemset/problem/1404/E) (建圖很有趣的有趣的怪題)
[CodeForces - 793G Oleg and chess](https://codeforces.com/problemset/problem/793/G) (閱讀題，建圖很有趣，可以用線段樹或是 bitset 優化，推薦 bitset 程式碼會短很多)
[ICPC Thailand National Competition 2024 Problem C. Cattering](https://codeforces.com/gym/105335/problem/C) (這題好像只能 flow 或 Hopcroft-Karp)
[Codeforces gym 102433 I. Error Correction](https://codeforces.com/gym/102433/attachments) (閱讀題，建圖很有趣)
[ECPC2016 Problem C. The Wall](https://codeforces.com/gym/101147/problem/C) (坐標系 有趣)
[AtCoder Beginner Contest 320 - Slot Strategy 2 (Hard)](https://atcoder.jp/contests/abc320/tasks/abc320_g) (這就是我說的，不需要直接建右集合的題目，可以用 map 優化)
----
## 參考資料
- D.B.West - Introduction to Graph Theory 2/e
- Introduction to Algorithms, Fourth Edition
- [台師大演算法筆記 - matching](https://web.ntnu.edu.tw/~algo/Matching.html)
- [CP-algorithms Kuhn's Algorithm for Maximum Bipartite Matching](https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html)
- [海大競程 flow and match](https://hackmd.io/@LeeShoWhaodian/2024flow#/6) (這裡寫的名稱是錯的)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/1/31
Sign in with Wallet
Connect another wallet