---
tags: 成大高階競技程式設計 2021
---
# 2021 Week17 - Matching
註：:bulb: 代表相對少見、較進階或與主題關聯性較低的內容，讀者可自行斟酌觀看。
---
# 匹配（Matching）
# 最大匹配（Maximum Cardinality Matching）
```graphviz
graph {
A [label="A", style=filled];
B [label="B", style=filled];
C [label="C"];
D [label="D", style=filled];
E [label="E", style=filled];
F [label="F", style=filled];
G [label="G", style=filled];
A -- B [style=bold, color="#B000B0"];
A -- C;
A -- D;
C -- F;
B -- E;
D -- E [style=bold, color="#B000B0"];
F -- G [style=bold, color="#B000B0"];
}
```
> 二個節點有邊相連時，彼此可以形成一對，同時不再與其他點配對。
**一個圖 $G$ 上兩兩不相鄰的邊組成一個集合 $M$，稱為圖上的一個匹配（matching）。**
> * 匹配邊（matched edge）：$M$ 中的邊
> * 非匹配邊（unmatched edge）
> * 匹配點（matched vertex）：某個匹配邊的端點
> * 非匹配點（unmatched vertex）
> <br>
> * 最大匹配（maximum matching）：所有 $G$ 的匹配中，匹配邊最多的匹配
> * 完美匹配（perfect matching）：$G$ 的所有節點均為匹配點
<hr class="thin">
#### 交錯路徑
```graphviz
graph {
rankdir=LR;
A [label=""];
node [label="", style=filled];
A -- B;
B -- C [style=bold, color="#B000B0"];
C -- D;
D -- E [style=bold, color="#B000B0"];
}
```
$G$ 上的一條路徑，邊由 $M$ 的匹配邊與非匹配邊交錯組成，且起點為非匹配點，稱為 $M$-交錯路徑（$M$-alternating path）。
<hr class="thin">
#### 可擴增路徑
```graphviz
graph {
rankdir=LR;
A [label=""];
B [label="", style=filled];
C [label="", style=filled];
D [label=""];
A -- B;
B -- C [style=bold, color="#B000B0"];
C -- D;
}
```
**一條 $M$-交錯路徑（$M$-alternating path），起點與終點皆為非匹配點，稱為 $M$-可擴增路徑（$M$-augmenting path）。**
> 「$M$-」代表它跟匹配 $M$ 有關。
將一條 $M$-可擴增路徑 $P$ 擴增，匹配邊變成非匹配邊，非匹配邊變成匹配邊，
可以得到一個更大的匹配 $M'=M\;\triangle\; P=(M\cup P)\setminus (M\cap P)$。
> $\triangle$ 是對稱差（symmetric difference）。
> ```graphviz
> graph {
> rankdir=LR;
> label="Augmented :";
> fontsize=15;
> labelloc=t;
> labeljust=l;
>
> A [label="", style=filled];
> B [label="", style=filled];
> C [label="", style=filled];
> D [label="", style=filled];
>
> A -- B [style=bold, color="#B000B0"];
> B -- C;
> C -- D [style=bold, color="#B000B0"];
> }
> ```
<hr class="dotted">
### Berge's lemma
:::danger
**一個匹配 $M$ 是最大匹配若且唯若不存在 $M$-可擴增路徑。**
:::
> #### 證明:bulb:
>
> 1. 如果存在 $M$-可擴增路徑，就可以得到更大的匹配，所以 $M$ 就不是最大匹配。
> 2. 如果不存在 $M$-可擴增路徑，對於任意一個匹配 $M'$，
> 考慮 $M\;\triangle\;M'$ 所構成的圖 $H$，$\Delta(H)\le 2$，
> 所以 $H$ 的每個連通部分要不是路徑就是環。
>
> 如果是路徑的話，一定是 $M$-交錯路徑，
> 但是根據假設，它不是 $M$-可擴增路徑，
> 所以路徑上屬於 $M$ 的邊不少於屬於 $M'$ 的邊；
> 如果是環的話，環上屬於 $M$ 的邊跟屬於 $M'$ 的邊一樣多。
>
> 得到結論，$|M|\ge |M'|$，所以 $M$ 是最大匹配。
>
> > $\Delta(G)$ 代表圖 $G$ 的最大度數（maximum degree）。
<hr class="thin">
#### 奇點／偶點
```graphviz
digraph {
rankdir=LR;
A [label="", color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
C [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
D [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
A -> B [arrowhead=o];
B -> C [style=bold, arrowhead=o, color="#B000B0"];
C -> D [arrowhead=o];
D -> E [style=bold, arrowhead=o, color="#B000B0"];
}
```
一條交錯路徑上，距離起點基數條邊的點為**奇點（odd vertex）**；
距離起點偶數條邊的點為**偶點（even vertex）**（包含起點）。
> 交錯路徑並沒有真的起點，端看我們怎麼看它，
> 而在尋找時，通常以某個非匹配點作為起點開始。
<hr class="dashed">
## 二分圖最大匹配（Maximum Cardinality Bipartite Matching）
> 二分圖，代表節點可以被分為二個集合，同個集合內的節點不能有邊相連。
```graphviz
graph {
rankdir=LR;
subgraph cluster_X {
style=dashed;
label="X";
A [label="0", fontcolor="#FF0000", style=filled];
B [label="1", fontcolor="#FF0000", style=filled];
C [label="2", fontcolor="#FF0000"];
}
subgraph cluster_Y {
style=dashed;
label="Y";
a[label="0", fontcolor="#0000FF", style=filled];
b[label="1", fontcolor="#0000FF", style=filled];
c[label="2", fontcolor="#0000FF"];
}
A -- a [style=bold, color="#B000B0"];
A -- c;
B -- a;
B -- b [style=bold, color="#B000B0"];
C -- a;
C -- b;
}
```
因為可擴增路徑長度是奇數，二分圖上的一條可擴增路徑，兩個非匹配點一定分屬集合 $X,Y$。
因此在找可擴增路徑時，只需要**以 $X$ 中的非匹配點為起點**就可以了。
> 交錯路徑上，**$X$ 的點都是偶點，$Y$ 的點都是奇點**。
```graphviz
digraph {
rankdir=LR;
A [label="0", fontcolor="#FF0000", style=filled, fillcolor=lightgray, color="#FF0000"];
C [label="2", fontcolor="#FF0000", color="#FF0000"];
a[label="0", fontcolor="#0000FF", style=filled, fillcolor=lightgray, color="#0000FF"];
c[label="2", fontcolor="#0000FF", color="#0000FF"];
C -> a [arrowhead=o];
a -> A [style=bold, color="#B000B0", arrowhead=o];
A -> c [arrowhead=o];
}
```
以一個某個 $X$ 中的起點，沿著不同的交錯路徑往下找，
交錯路徑 $P_1,P_2$ 可能會出現重疊的情況，
但是在 $P_2$ 上，$P_1$ 的偶點還是偶點，奇點還是奇點，
也就是說 $P_1$ 從交會點往下走，與 $P_2$ 從交會點往下走，
是否能變成可擴增路徑的結果是一樣的，而且最終也只能選擇一條，
所以**當路徑遇到已經被拜訪過的節點，不考慮往此節點繼續走**。
```graphviz
digraph {
rankdir=LR;
A [label="0", fontcolor="#FF0000", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="1", fontcolor="#FF0000", style=filled, fillcolor=lightgray, color="#FF0000"];
C [label="2", fontcolor="#FF0000", color="#FF0000"];
a[label="0", fontcolor="#0000FF", style=filled, fillcolor=lightgray, color="#0000FF"];
b[label="1", fontcolor="#0000FF", style=filled, fillcolor=lightgray, color="#0000FF"];
c[label="2", fontcolor="#0000FF", color="#0000FF"];
C -> a [arrowhead=o];
a -> A [style=bold, arrowhead=o, color="#B000B0"];
A -> c [arrowhead=o];
C -> b [arrowhead=o];
b -> B [style=bold, arrowhead=o, color="#B000B0"];
B -> a [style=dotted, arrowhead=o];
}
```
> **奇點到偶點是匹配邊，偶點到奇點是非匹配邊**，
> 因為奇點的匹配邊唯一，只會到唯一的偶點（並且沒被拜訪過），
> **cross edge 只可能是「偶點到奇點」或「偶點到偶點」的邊**；
> 又因為二分圖沒有偶點到偶點（$X$ 到 $X$）的邊，
> 因此遇到被拜訪過的點，也就是 **cross edge，一定是偶點到奇點的邊**。
<hr class="dotted">
### Augmenting Path Algorithm
依序以 $X$ 中每個非匹配點為起點，進行 DFS，尋找可擴增路徑，
如果有找到的話就進行擴增，最後就可以得到最大匹配。
> 為什麼可以這樣做呢？
> 如果演算法結束後，每個 $X$ 的非匹配點都沒有可擴增路徑，
> 根據 Berge's lemma，匹配就是最大匹配了。
>
> 首先擴增只會把某些非匹配點變為匹配點，所以演算法結束後還是 $X$ 的非匹配點，
> 代表一開始它就是 $X$ 的非匹配點，我們已經確認過不存在以它為起點的可擴增路徑。
> 因此剩下要確認的就是，**原本沒有可擴增路徑的點，在進行擴增後，還是沒有可擴增路徑**。
>
> #### 證明:bulb:
> 假設對於可擴增路徑 $P_v=v_0\dots v_k$ 進行擴增，
> 造成另一個 $X$ 的非匹配點 $u_1$，因此多了一條可擴增路徑 $P_u=u_1\dots u_2$，
> 則 $P_u$ 與 $P_v$ 一定有部分重疊路徑 $v_i\dots v_j$。
>
> ```graphviz
> digraph {
> rankdir=LR;
> label="Before :";
> fontsize=30;
> labelloc=t;
> labeljust=l;
>
> A [label="v0", fontcolor="#FF0000", color="#FF0000"];
> B [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> C [label="vi", fontcolor="#FF0000", style=filled, fillcolor=lightgray, color="#FF0000"];
> D [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> F [label="vj", fontcolor="#0000FF", style=filled, fillcolor=lightgray, color="#0000FF"];
> G [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> H [label="vk", fontcolor="#0000FF", color="#0000FF"];
>
> a [label="u1", fontcolor="#FF0000", style=dashed];
> b [label="", style="filled, dashed", fillcolor=lightgray];
> c [label="", style="filled, dashed", fillcolor=lightgray];
> d [label="u2", fontcolor="#0000FF", style=dashed];
>
> A -> B [arrowhead=o];
> B -> C [style=bold, arrowhead=o, color="#B000B0"];
> C -> D [arrowhead=o];
> D -> E [style=bold, arrowhead=o, color="#B000B0"];
> E -> F [arrowhead=o];
> F -> G [style=bold, arrowhead=o, color="#B000B0"];
> G -> H [arrowhead=o];
>
> b -> a [style=dashed, dir=none];
> c -> b [style="bold, dashed", dir=none, color="#B000B0"];
> F :ne -> c [style=dashed, dir=none];
> d -> C :sw [style=dashed, dir=none];
> }
> ```
> >
> ```graphviz
> digraph {
> rankdir=LR;
> label="After :";
> fontsize=30;
> labelloc=t;
> labeljust=l;
>
> A [label="v0", fontcolor="#FF0000", style=filled, fillcolor=lightgray];
> B [label="", style=filled, fillcolor=lightgray];
> C [label="vi", fontcolor="#FF0000", style=filled, fillcolor=lightgray, color="#FF0000"];
> D [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> F [label="vj", fontcolor="#0000FF", style=filled, fillcolor=lightgray, color="#0000FF"];
> G [label="", style=filled, fillcolor=lightgray];
> H [label="vk", fontcolor="#0000FF", style=filled, fillcolor=lightgray];
>
> a [label="u1", fontcolor="#FF0000", style=dashed, color="#FF0000"];
> b [label="", style="filled, dashed", fillcolor=lightgray, color="#0000FF"];
> c [label="", style="filled, dashed", fillcolor=lightgray, color="#FF0000"];
> d [label="u2", fontcolor="#0000FF", style=dashed, color="#0000FF"];
>
> A -> B [style=bold, dir=none, color="#B000B0"];
> B -> C [dir=none];
> C -> D [style=bold, dir=back, arrowtail=o, color="#B000B0"];
> D -> E [dir=back, arrowtail=o];
> E -> F [dir=back, style=bold, arrowtail=o, color="#B000B0"];
> F -> G [dir=none];
> G -> H [dir=none, style=bold, color="#B000B0"];
>
> b -> a [style=dashed, dir=back, arrowtail=o];
> c -> b [style="bold, dashed", dir=back, arrowtail=o, color="#B000B0"];
> F :ne -> c [style=dashed, dir=back, arrowtail=o];
> d -> C :sw [style=dashed, dir=back, arrowtail=o];
> }
> ```
>
> $(v_i,v_{i+1})$ 與 $(v_{j-1},v_j)$ 擴增前一定是非匹配邊，因此如圖所示，
> 擴增前 $u_1$ 應該要有可擴增路徑（$u_1\dots v_k$），與假設衝突，原命題成立。
>
> > 如果 $(v_i,v_{i+1})$ 或 $(v_{j-1},v_j)$ 擴增前是匹配邊，擴增後是非匹配邊，
> > $(P_u\setminus P_v)$ 上要有另一條匹配邊連接著 $v_i$ 或 $v_j$，
> > 但是 $(v_{i-1},v_i)$ 與 $(v_j,v_{j+1})$ 也是匹配邊，這就不是匹配了。
<hr class="dotted">
實作上，**DFS 只停留在 $X$ 的點**，**每次走一條非匹配邊**，
若此時遇到的是 $Y$ 的非匹配點，就找到可擴增路徑了；
如果是 $Y$ 的匹配點，則**直接接著再走一條匹配邊**，到另一個 $X$ 的點。
> $Y$ 的點的匹配邊唯一，這就是為什麼只以 $X$ 的點為基準，
> 並且每次走二條邊（**一條非匹配邊 $+$ 一條匹配邊**）。
```cpp!
class BipartiteMatching {
vector<bool> vis;
vector<int> mx{}, my{};
bool dfs(const vector<vector<int>>& adj, int x) {
for (auto& y : adj[x]) {
if (vis[y]) continue;
vis[y] = true;
if (my[y] == -1 || dfs(adj, my[y])) {
mx[x] = y, my[y] = x;
return true;
}
}
return false;
}
public:
pair<vector<int>, vector<int>> operator()(const vector<vector<int>>& adj, int ny) {
vis.resize(ny), mx.assign(adj.size(), -1), my.assign(ny, -1);
int c{0};
for (int x{0}; x < adj.size(); ++x) {
fill(vis.begin(), vis.end(), false);
if (dfs(adj, x)) ++c;
}
return {move(mx), move(my)};
}
};
```
每個點進行一次 DFS，複雜度為 $O(|V|(|V|+|E|))=O(|V||E|)$。
<hr class="dotted">
#### greedy matching
先找到一個極大匹配，不要從空的匹配開始。
> 一個極大匹配，不為任何其他匹配的子集。
```cpp!
for (int x{0}; x < adj.size(); ++x) // greedy matching
for (auto& y : adj[x]) {
if (my[y] != -1) continue;
mx[x] = y, my[y] = x, ++c;
break;
}
```
<hr class="dashed">
### Hopcroft-Karp Algorithm
Augmenting Path Algorithm 透過 DFS 搜尋，
常常去找較長的可擴增路徑，導致複雜度並不優異；
Hopcroft-Karp Algorithm 改為尋找最短的可擴增路徑，
我們沒辦法事先知道最短可擴增路徑的起點是誰，
因此以所有 $X$ 的非匹配點當作樹根，進行 BFS。
> 如果分別從 $x_i,x_j$ 開始尋找，當它們交會時，
> 在 $x_i$ 繼續找下去的結果與 $x_j$ 一致，
> 所以只從 $x_i$ 找下去即可，與之前的結論相同，
> **當路徑遇到已經被拜訪過的節點，不往此節點進行搜尋**。
這邊只是「尋找」可擴增路徑，還沒有進行擴增，所以路徑重疊沒關係。
```graphviz
digraph {
rankdir=LR;
A [label="xi", fontcolor="#FF0000", color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
C [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
D1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", color="#0000FF"];
D2 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
a [label="xj", fontcolor="#FF0000", color="#FF0000"];
b [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
c [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
A :e -> B :nw [arrowhead=o];
B -> C [style=bold, arrowhead=o, color="#B000B0"];
C :ne -> D1 :w [arrowhead=o];
D1 -> E [style=bold, arrowhead=o, color="#B000B0"];
E -> F [arrowhead=o];
C :se -> D2 :w [arrowhead=o];
a -> b [arrowhead=o];
b -> c [style=bold, arrowhead=o, color="#B000B0"];
c :e -> B :sw [style=dashed, arrowhead=o];
}
```
那為什麼不能跟之前一樣保留一條路徑就好呢？
因為 $x_i$ 可能有多條可擴增路徑，最後不一定會擴增重疊的部分。
```graphviz
digraph {
rankdir=LR;
A [label="xi", fontcolor="#FF0000", color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
C [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
D1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", color="#0000FF"];
D2 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
G [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
H [label="", color="#0000FF"];
I [label="", color="#0000FF"];
D3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
J [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
K [label="", color="#0000FF"];
a [label="xj", fontcolor="#FF0000", color="#FF0000"];
b [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
c [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
A -> B [arrowhead=o];
B -> C [style=bold, arrowhead=o, color="#B000B0"];
C :ne -> D1 :w [arrowhead=o];
D1 -> E [style=bold, arrowhead=o, color="#B000B0"];
E -> F [arrowhead=o];
C :e -> D2 :nw [arrowhead=o];
D2 -> G [style=bold, arrowhead=o, color="#B000B0"];
G -> H [arrowhead=o];
G -> I [arrowhead=o];
C :se -> D3 :nw [arrowhead=o];
D3 -> J [style=bold, arrowhead=o, color="#B000B0"];
J -> K [arrowhead=o];
a -> b [arrowhead=o];
b -> c [style=bold, arrowhead=o, color="#B000B0"];
c :e -> D3 :sw [style=dashed, arrowhead=o];
}
```
1. 重複步驟 $2,3$，直到沒有可擴增路徑為止
2. 把**所有的 $X$ 非匹配點**當作樹根，透過 BFS，尋找**所有最短可擴增路徑**
3. 對於 BFS 森林的每個樹葉，透過 **DFS 回溯，找可擴增路徑並擴增**
> 可擴增路徑有可能重疊，因此在擴增後，要把這條路徑**從 BFS 森林中移除**。
>
> 不是有 $k$ 條可擴增路徑，就代表可以擴增 $k$ 次。
步驟 $2$ 嚴格來說，是找到一個「點不重複的最短可擴增路徑」的極大集合
（a maximal set of vertex-disjoint shortest augmenting paths）；
換句話說，這些路徑都可以進行擴增，並且擴增後，就不存在其他長度相等的可擴增路徑。
> 下面二種情況都是極大集合：
>
> ```graphviz
> digraph {
> rankdir=LR;
>
> A [label="xi", fontcolor="#FF0000", color="#FF0000"];
> B [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> C [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> D1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> F [label="", color="#0000FF"];
> D2 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> G [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> H [label="", color="#0000FF"];
> I [label="", color="#0000FF"];
> D3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> J [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> K [label="", color="#0000FF"];
>
> a [label="xj", fontcolor="#FF0000", color="#FF0000"];
> b [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> c [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
>
> A -> B [dir=back, arrowtail=o];
> B -> C [style=bold, dir=back, arrowtail=o, color="#B000B0"];
> C :ne -> D1 :w [dir=none];
> D1 -> E [style=bold, dir=none, color="#B000B0"];
> E -> F [dir=none];
> C :e -> D2 :nw [dir=none];
> D2 -> G [style=bold, dir=none, color="#B000B0"];
> G -> H [dir=none];
> G -> I [dir=none];
> C :se -> D3 :nw [dir=back, arrowtail=o];
> D3 -> J [style=bold, dir=back, arrowtail=o, color="#B000B0"];
> J -> K [dir=back, arrowtail=o];
>
> a -> b [dir=none];
> b -> c [style=bold, dir=none, color="#B000B0"];
> c :e -> D3 :sw [style=dashed, dir=none];
> }
> ```
>
> ```graphviz
> digraph {
> rankdir=LR;
>
> A [label="xi", fontcolor="#FF0000", color="#FF0000"];
> B [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> C [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> D1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> F [label="", color="#0000FF"];
> D2 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> G [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> H [label="", color="#0000FF"];
> I [label="", color="#0000FF"];
> D3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> J [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> K [label="", color="#0000FF"];
>
> a [label="xj", fontcolor="#FF0000", color="#FF0000"];
> b [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> c [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
>
> A -> B [dir=back, arrowtail=o];
> B -> C [style=bold, dir=back, arrowtail=o, color="#B000B0"];
> C :ne -> D1 :w [dir=none];
> D1 -> E [style=bold, dir=none, color="#B000B0"];
> E -> F [dir=none];
> C :e -> D2 :nw [dir=back, arrowtail=o];
> D2 -> G [style=bold, dir=back, arrowtail=o, color="#B000B0"];
> G -> H [dir=back, arrowtail=o];
> G -> I [dir=none];
> C :se -> D3 :nw [dir=none];
> D3 -> J [style=bold, dir=back, arrowtail=o, color="#B000B0"];
> J -> K [dir=back, arrowtail=o];
>
> a -> b [dir=back, arrowtail=o];
> b -> c [style=bold, dir=back, arrowtail=o, color="#B000B0"];
> c :e -> D3 :sw [style=dashed, dir=back, arrowtail=o];
> }
> ```
乍看之下，BFS 森林不容易紀錄，因為樹之間可能重疊，有相同的子樹；
換句話說，就是像上圖一樣有虛邊。
不過我們只在意最短可擴增路徑，所以如果 $x_j$ 到交會點的長度，
大於 $x_i$ 到交會點的長度，就不用考慮它了；
因此這邊記錄每個節點的深度（也就是到路徑起點的距離），
搭配原先的圖，就可以推斷出 BFS 森林。
<hr class="dotted">
BFS 時，一樣以 $X$ 的點為基準，每次走一條非匹配邊，如果需要繼續就直接再走匹配邊；
而 DFS 時，因為從 $Y$ 的點開始回溯，一樣一次走一條非匹配邊，
如果要繼續回溯，就直接走匹配邊，只差在是以 $Y$ 的點為基準。
```cpp!
// Hopcroft–Karp algorithm - O(E√V)
class BipartiteMatching {
vector<vector<int>> adjy;
vector<int> dx, dy, mx, my;
bool dfs(const vector<vector<int>>& adjx, int y) {
for (auto& x : adjy[y]) {
if (dx[x] + 1 != dy[y]) continue;
if (mx[x] == -1 || dfs(adjx, mx[x])) {
my[y] = x, mx[x] = y;
dy[y] = -1; // remove from bfs forest
return true;
}
}
dy[y] = -1; // remove from bfs forest
return false;
}
bool bfs(const vector<vector<int>>& adjx) {
fill(dx.begin(), dx.end(), -1);
fill(dy.begin(), dy.end(), -1);
queue<int> qu{}, qu2{};
for (int x{0}; x < adjx.size(); ++x) // use all unmatched x's as roots
if (mx[x] == -1) qu.push(x), dx[x] = 0;
bool found{false};
while (!qu.empty() && !found) { // stop at the level found
while (!qu.empty()) {
auto x{qu.front()}; qu.pop();
for (auto& y : adjx[x])
if (dy[y] == -1 && my[y] != x) {
dy[y] = dx[x] + 1;
if (my[y] == -1) found = true;
else qu2.push(my[y]), dx[my[y]] = dy[y] + 1;
}
}
qu.swap(qu2);
}
return found;
}
public:
pair<vector<int>, vector<int>> operator()(const vector<vector<int>>& adjx, int ny) {
adjy.assign(ny, {});
for (int x{0}; x < adjx.size(); ++x)
for (auto& y : adjx[x]) adjy[y].push_back(x);
dx.resize(adjx.size()), dy.resize(ny), mx.assign(adjx.size(), -1), my.assign(ny, -1);
int c{0};
while (bfs(adjx)) {
for (int y{0}; y < ny; ++y)
if (my[y] == -1 && dy[y] != -1) c += dfs(adjx, y);
}
return {move(mx), move(my)};
}
};
```
<hr class="thin">
:::danger
（引理 1.）對於圖 $G$ 上的二個匹配 $M_a,M_b$，如果 $|M_a|\gt|M_b|$，則 $M_b$ 至少有 $|M_a|-|M_b|$ 條（點不重複的）可擴增路徑。
:::
考慮子圖 $H=M_a\;\triangle\; M_b$，$H$ 的連通部分不是路徑就是環，
而且一定是 $M_a$ 的邊與 $M_b$ 的邊交錯，因此連通部分有三種可能，
$M_a$ 的邊比 $M_b$ 的邊多 $1$；$M_a$ 的邊與 $M_b$ 的邊一樣多；$M_a$ 的邊比 $M_b$ 的邊少 $1$。
因為 $M_a$ 的匹配邊比 $M_b$ 多了 $|M_a|-|M_b|$ 條，所以至少**有這麼多的連通部分**，
$M_a$ 的邊會比 $M_b$ 的邊多 $1$，而這樣的連通部分，就**是 $M_b$ 的可擴增路徑**。
```graphviz
digraph {
rankdir=LR;
subgraph cluster_3 {
label="Mb 的邊多 1：";
fontsize=20;
labelloc=t;
labeljust=l;
J [label=""];
K [label=""];
L [style=invis];
M [style=invis];
J -> K [label="Mb", dir=both, arrowhead=ldiamond, arrowtail=rdiamond];
K -> L [style=invis];
L -> M [style=invis];
}
subgraph cluster_2 {
label="一樣多：";
fontsize=20;
labelloc=t;
labeljust=l;
E [label=""];
F [label=""];
G [label=""];
H [label=""];
I [style=invis];
E :s -> F [label="Ma", dir=both, arrowhead=rdiamond, arrowtail=ldiamond, color=lightgray];
F -> G :sw [label="Mb", dir=both, arrowhead=ldiamond, arrowtail=rdiamond];
E :n -> H [label="Mb", dir=both, arrowhead=ldiamond, arrowtail=rdiamond];
H -> G :nw [label="Ma", dir=both, arrowhead=rdiamond, arrowtail=ldiamond, color=lightgray];
G -> I [style=invis];
}
subgraph cluster_1 {
label="Ma 的邊多 1：";
fontsize=20;
labelloc=t;
labeljust=l;
A [label=""];
B [label=""];
C [label=""];
D [label=""];
A -> B [label="Ma", dir=both, arrowhead=rdiamond, arrowtail=ldiamond, color=lightgray];
B -> C [label="Mb", dir=both, arrowhead=ldiamond, arrowtail=rdiamond];
C -> D [label="Ma", dir=both, arrowhead=rdiamond, arrowtail=ldiamond, color=lightgray];
}
}
```
<hr class="thin">
**每次的最短可擴增路徑長度都比前一次大。**
> 匹配 $M1$，對 $k$ 條長度 $l$ 的最短可擴增路徑 $p_1\dots p_k$ 擴增，
> 變為匹配 $M2=M1\;\triangle\; (p_1\cup \dots \cup p_k)$，而對於 $M2$ 的任意一條可擴增路徑 $p$，
>
> > 如果 $p$ 與 $p_1\dots p_k$ 沒有任何重疊部分，
> > 因為我們已經擴增了「最短可擴增路徑的極大集合」，
> > $p$ 的長度自然就大於 $l$，以下討論重疊的情況。
>
> $M2$ 再對 $p$ 擴增後，變為匹配 $M3=M2\;\triangle\; p$，
> 根據引理 1.，$M3$ 比 $M1$ 多了 $k+1$ 個匹配數，
> 代表 $M1$ 至少要有 $k+1$ 條可擴增路徑，並且是在 $M1\;\triangle\; M3$ 中，
> 因為 $M1$ 的最短可擴增路徑長度為 $l$，$M1\;\triangle\; M3$ **至少有 $(k+1)\cdot l$ 條邊**；
> 而 $M1\;\triangle\; M3=(p_1\cup \dots \cup p_k)\;\triangle\; p$，$p$ 與 $p_1\cup \dots \cup p_k$ 有重疊的話，
> **最多只能有 $k\cdot l+|p|-1$ 條邊**，所以得到結論，**$|p|$ 大於 $l$**。
>
> $(k+1)\cdot l\le |M1\;\triangle\; M3|=|(p_1\cup \dots \cup p_k)\;\triangle\; p|\le k\cdot l+|p|-1\\\to|p|\gt l$
<hr class="thin">
**演算法在至多 $2\sqrt V$ 次後，達到最大匹配。**
> **經過 $\sqrt V$ 次**，此時的匹配為 $M'$，可擴增路徑**長度至少 $\sqrt V$**；
> 與最大匹配 $M$，$M\;\triangle\; M'$ 的連通部分為 $M'$ 的交錯路徑或交錯環，
> 而可擴增路徑長度至少為 $\sqrt V$，代表**至多有 $\sqrt V$ 條（點不重複的）可擴增路徑**；
> 這代表 **$M'$ 的匹配數最多比 $M$ 的匹配數少了 $\sqrt V$ 個**，
> 所以**最多再經過 $\sqrt V$ 次後，就會達到最大匹配**。
<hr class="thin">
每次一個 BFS 與一個 DFS，總共 $2\sqrt V$ 次，**複雜度為 $O(|E|\sqrt{|V|})$**。
<hr class="dashed">
## 一般圖最大匹配（Maximum Cardinality Matching in a general graph）
### Edmonds' Blossom Algorithm:bulb:
```graphviz
graph {
rankdir=LR;
S0 [label="root", color="#FF0000"];
S1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
S2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
S3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
C [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
D [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
}
S0 -- S1;
S1 -- S2 [style=bold, color="#B000B0"];
S2 -- S3;
S3 -- A [style=bold, color="#B000B0"];
A :se -- B;
B :e -- C [style=bold, color="#B000B0"];
A :ne -- D;
D :e -- E [style=bold, color="#B000B0"];
C -- E [style=dashed];
A :e -- C [style=invis];
A :e -- E [style=invis];
A :e -- D [style=invis];
}
```
> 前面說到，因為奇點到偶點只能走唯一的匹配邊，
> > 且到為匹配點的奇點時，會馬上走匹配邊到偶點，
> > 確保不會有奇點到奇點的 cross edge 出現。
>
> 所以 cross edge 可能是「偶點到奇點」或「偶點到偶點」的邊，
> 而偶點到奇點的邊，在二分圖時已經討論過了。
一般圖會出現偶點到偶點的 cross edge，形成一個奇圈（odd-length cycle），稱作花（blossom）。
```graphviz
digraph {
rankdir=LR;
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
C [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
D [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
G [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
}
S0 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [arrowhead=o];
B :e -> C [dir=none, style=bold, color="#B000B0"];
A :ne -> D [arrowhead=o];
D :e -> E [dir=none, style=bold, color="#B000B0"];
E -> F [arrowhead=o];
F -> G [dir=none, style=bold, color="#B000B0"];
C -> G [style=dashed, dir=none];
A :e -> C [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
}
```
<hr class="thin">
花上的奇點只要從另一側過來，就可以搖身一變成為偶點，繼續尋找可擴增路徑。
```graphviz
digraph {
rankdir=LR;
S0 :n -> H :s [style=invis];
H -> I :s [style=invis];
H [style=invis];
I [style=invis];
H -> D [dir=back, arrowtail=o];
F -> I [arrowhead=o];
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
C [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
D [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
G [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
}
S0 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [arrowhead=o];
B :e -> C [dir=none, style=bold, color="#B000B0"];
A :ne -> D [arrowhead=o];
D :e -> E [dir=none, style=bold, color="#B000B0"];
E -> F [arrowhead=o];
F -> G [dir=none, style=bold, color="#B000B0"];
C -> G [style=dashed, dir=none];
A :e -> C [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
J [style=invis];
J -> B :s [dir=back, arrowtail=o];
}
```
<hr class="thin">
因為花上都是偶點，所以可以進行縮花（blossom contraction），變為一個假點。
> 縮花是為了讓圖逐漸變小，減少運算量，也可以選擇不縮花。
```graphviz
digraph {
rankdir=LR;
S0 [label="root", color="#FF0000"];
S1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
S2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
S3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
S4 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
subgraph cluster_blossom {
label="Blossom";
fontsize=15;
labelloc=t;
labeljust=l;
A [shape=doublecircle, label="base", style=filled, fillcolor=lightgray, color="#FFA500"];
}
S0 -> S1;
S1 -> S2 [style=bold, color="#B000B0"];
S2 -> S3;
S3 -> A [style=bold, color="#B000B0"];
A -> S4;
}
```
<hr class="thin">
1. 依序以每個非匹配點當作樹根，進行步驟 $2,3$
2. 透過 BFS 尋找可擴增路徑
* 出現花就縮花，花上的奇點變成偶點，繼續尋找
* 找到可擴增路徑就結束搜尋
3. 沿著可擴增路徑拆花並擴增
> 正確性論證與 Augmenting path algorithm 相同。
<hr class="dotted">
實作上，花雖然是一個圈，但還是有方向性地分為二側，
因此我們對二側原本的偶點，分別記錄 cross edge，
以利之後可以繞花，到達另一側；
> 也可以對二側的所有點進行記錄。
```graphviz
digraph {
rankdir=LR;
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
C [label="c2", style=filled, fillcolor=lightgray, color="#FF0000"];
D [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"];
}
S0 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=o];
B :e -> C [dir=none, style=bold, color="#B000B0"];
A :ne -> D [dir=back, arrowtail=o];
D :e -> E [dir=none, style=bold, color="#B000B0"];
E -> F [dir=back, arrowtail=o];
F -> G [dir=none, style=bold, color="#B000B0"];
C :n -> G [style=dashed, arrowhead=curve];
E -> G [style=dashed, arrowhead=curve];
E -> C [style=dashed, arrowhead=curve];
G :s -> C [style=dashed, arrowhead=curve];
A :e -> C [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
}
```
雖然花上的奇點都變為偶點，實際上還是需要知道它是哪種情況，
才能決定要不要繞花，或是照著原本的路徑回去就好。
<hr class="dotted">
```graphviz
digraph {
rankdir=LR;
H [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
I [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
J [label="", color="#0000FF"];
A -> H [dir=back, arrowtail=o];
H -> I [dir=none, style=bold, color="#B000B0"];
I -> J [dir=back, arrowtail=o];
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=15;
labelloc=t;
labeljust=l;
A [shape=doublecircle, label="base", style=filled, fillcolor=lightgray, color="#FFA500"];
}
S0 -> A [dir=none, style=bold, color="#B000B0"];
}
```
<hr class="thin">
先拆花。
```graphviz
digraph {
rankdir=LR;
H [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
I [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
J [label="", color="#0000FF"];
D -> H [dir=back, arrowtail=o];
H -> I [dir=none, style=bold, color="#B000B0"];
I -> J [dir=back, arrowtail=o];
J -> G [style=invis];
I -> F [style=invis];
H -> E [style=invis];
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
C [label="c2", style=filled, fillcolor=lightgray, color="#FF0000"];
D [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"];
}
S0 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=o];
B :e -> C [dir=none, style=bold, color="#B000B0"];
A :ne -> D [dir=back, arrowtail=o];
D :e -> E [dir=none, style=bold, color="#B000B0"];
E -> F [dir=back, arrowtail=o];
F -> G [dir=none, style=bold, color="#B000B0"];
C -> G [style=dashed, dir=none];
A :e -> C [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
}
```
<hr class="thin">
到花之前正常進行擴增。
```graphviz
digraph {
rankdir=LR;
H [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
I [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
J [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
D -> H [dir=none, style=bold, color="#B000B0"];
H -> I [dir=none];
I -> J [dir=none, style=bold, color="#B000B0"];
J -> G [style=invis];
I -> F [style=invis];
H -> E [style=invis];
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
C [label="c2", style=filled, fillcolor=lightgray, color="#FF0000"];
D [label="m[y]", style=filled, fillcolor=lightgray, color="#FFA500"];
E [label="y", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"];
}
S0 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=o];
B :e -> C [dir=none, style=bold, color="#B000B0"];
A :ne -> D [dir=back, arrowtail=o];
D :e -> E [dir=none, style=bold, color="#B000B0"];
E -> F [dir=back, arrowtail=o];
F -> G [dir=none, style=bold, color="#B000B0"];
C -> G [style=dashed, dir=none];
A :e -> C [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
}
```
<hr class="thin">
進入花的第一條匹配邊一定要變為非匹配邊。
```graphviz
digraph {
rankdir=LR;
H [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
I [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
J [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
D -> H [dir=none, style=bold, color="#B000B0"];
H -> I [dir=none];
I -> J [dir=none, style=bold, color="#B000B0"];
J -> G [style=invis];
I -> F [style=invis];
H -> E [style=invis];
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
C [label="c2", style=filled, fillcolor=lightgray, color="#FF0000"];
D [label="m[y]", style=filled, fillcolor=lightgray, color="#FF0000"];
E [label="y", color="#0080FF"];
F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"];
}
S0 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=o];
B :e -> C [dir=none, style=bold, color="#B000B0"];
A :ne -> D [dir=back, arrowtail=o];
D :e -> E [dir=none];
E -> F [dir=back, arrowtail=o];
F -> G [dir=none, style=bold, color="#B000B0"];
C -> G [style=dashed, dir=none];
A :e -> C [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
}
```
<hr class="thin">
遇到花上原本的奇點，進行繞花；cross edge 會變為匹配邊。
> 前面是奇點暫時變為了偶點；
> 而現在這一側，奇點真正成為了偶點，偶點反而成為了奇點，
> 而對面一側，奇點則回歸奇點的身份。
```graphviz
digraph {
rankdir=LR;
H [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
I [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
J [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
D -> H [dir=none, style=bold, color="#B000B0"];
H -> I [dir=none];
I -> J [dir=none, style=bold, color="#B000B0"];
J -> G [style=invis];
I -> F [style=invis];
H -> E [style=invis];
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="p[c2]", color="#0000FF"];
C [label="c2", style=filled, fillcolor=lightgray, color="#FF0000"];
D [label="p[y]", style=filled, fillcolor=lightgray, color="#FF0000"];
E [label="y", color="#0080FF"];
F [label="p[c1]", color="#FF0000"];
G [label="c1", style=filled, fillcolor=lightgray, color="#0080FF"];
}
S0 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=o];
B :e -> C [dir=none];
A :ne -> D [style=invis];
D :e -> E [dir=none];
E -> F [dir=back, arrowtail=o];
F -> G [dir=none];
C -> G [style="dashed, bold", dir=none, color="#B000B0"];
A :e -> C [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
}
```
<hr class="thin">
將 cross edge 二側的交錯路徑分開，得到 $y\to p[c1]$ 與 $p[c2]\to root$ 二條可擴增路徑。
```graphviz
digraph {
rankdir=LR;
H [style=invis];
I [style=invis];
J [style=invis];
D -> H [style=invis];
H -> I [style=invis];
I -> J [style=invis];
J -> G [style=invis];
I -> F [style=invis];
H -> E [style=invis];
S0 [label="root", color="#FF0000"];
S1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
S2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
S3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="p[c2]", color="#0000FF"];
C [style=invis];
D [label="p[y]", style=dotted];
E [label="y", color="#0080FF"];
F [label="p[c1]", color="#FF0000"];
G [style=invis];
}
S0 -> S1 [dir=back, arrowtail=o];
S1 -> S2 [dir=none, style=bold, color="#B000B0"];
S2 -> S3 [dir=back, arrowtail=o];
S3 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=o];
B :e -> C [style=invis];
A :ne -> D [style=invis];
D :e -> E [dir=none, style=dotted];
E -> F [dir=back, arrowtail=o];
F -> G [style=invis];
C -> G [style=invis];
A :e -> C [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
}
```
<hr class="thin">
將 $y\to p[c1]$ 的起點看為 $y$，變成 $p[c1]\to y$，
就得到二條與原先 BFS 搜尋路徑方向一致的可擴增路徑。
```graphviz
digraph {
rankdir=LR;
H [style=invis];
I [style=invis];
J [style=invis];
D -> H [style=invis];
H -> I [style=invis];
I -> J [style=invis];
J -> G [style=invis];
I -> F [style=invis];
H -> E [style=invis];
S0 [label="root", color="#FF0000"];
S1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
S2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
S3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="p[c2]", color="#0000FF"];
C [style=invis];
D [label="p[y]", style=dotted];
E [label="y", color="#FF0000"];
F [label="p[c1]", color="#0000FF"];
G [style=invis];
}
S0 -> S1 [dir=back, arrowtail=o];
S1 -> S2 [dir=none, style=bold, color="#B000B0"];
S2 -> S3 [dir=back, arrowtail=o];
S3 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=o];
B :e -> C [style=invis];
A :ne -> D [style=invis];
D :e -> E [dir=none, style=dotted];
E -> F [dir=back, arrowtail=o];
F -> G [style=invis];
C -> G [style=invis];
A :e -> C [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
}
```
<hr class="thin">
> 花中有花呢？
>
> ```graphviz
> digraph {
> rankdir=LR;
>
> H [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> I [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> J [label="", color="#0000FF"];
>
> D -> H [dir=back, arrowtail=o];
> H -> I [dir=none, style=bold, color="#B000B0"];
> I -> J [dir=back, arrowtail=o];
>
> J -> G [style=invis];
> I -> F [style=invis];
> H -> E [style=invis];
>
> S0 [style=invis];
>
> subgraph cluster_blossom {
> label="Blossom";
> fontsize=20;
> labelloc=t;
> labeljust=l;
>
> A [shape=doublecircle, label="base", style=filled, fillcolor=lightgray, color="#FFA500"];
> B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
> C [shape=doublecircle, label="c2", style=filled, fillcolor=lightgray, color="#FFA500"];
> D [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
> E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
> G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"];
> }
>
> S0 -> A [dir=none, style=bold, color="#B000B0"];
>
> A :se -> B [dir=back, arrowtail=o];
> B :e -> C [dir=none, style=bold, color="#B000B0"];
> A :ne -> D [dir=back, arrowtail=o];
> D :e -> E [dir=none, style=bold, color="#B000B0"];
> E -> F [dir=back, arrowtail=o];
> F -> G [dir=none, style=bold, color="#B000B0"];
>
> C -> G [style=dashed, dir=none];
>
> A :e -> C [style=invis];
> A :e -> E [style=invis];
> A :e -> F [style=invis];
> A :e -> G [style=invis];
> }
> ```
>
> 一樣進行拆花。
>
> ```graphviz
> digraph {
> rankdir=LR;
>
> H [label="", style=filled, fillcolor=lightgray, color="#0000FF"];
> I [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> J [label="", color="#0000FF"];
>
> D -> H [dir=back, arrowtail=o];
> H -> I [dir=none, style=bold, color="#B000B0"];
> I -> J [dir=back, arrowtail=o];
>
> J -> G [style=invis];
> I -> F [style=invis];
> H -> E [style=invis];
>
> S0 [style=invis];
>
> subgraph cluster_blossom {
> label="Blossom";
> fontsize=20;
> labelloc=t;
> labeljust=l;
>
> subgraph cluster_blossom2 {
> label="Blossom";
> fontsize=10;
> labelloc=t;
> labeljust=l;
>
> A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
> A1 [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
> A2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> A3 [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
> A4 [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
>
> A :se -> A1 [dir=back, arrowtail=o];
> A1 -> A2 [dir=none, style=bold, color="#B000B0"];
> A :ne -> A3 [dir=back, arrowtail=o];
> A3 -> A4 [dir=none, style=bold, color="#B000B0"];
> A2 -> A4 [style=dashed, dir=none];
> }
>
> B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
> subgraph cluster_blossom3 {
> label="Blossom";
> fontsize=10;
> labelloc=t;
> labeljust=l;
>
> C [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
> C1 [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
> C2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> C3 [label="c2", style=filled, fillcolor=lightgray, color="#FFA500"];
> C4 [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
>
> C :se -> C1 [dir=back, arrowtail=o];
> C1 :e -> C2 [dir=none, style=bold, color="#B000B0"];
> C :ne -> C3 [dir=back, arrowtail=o];
> C3 :e -> C4 [dir=none, style=bold, color="#B000B0"];
> C2 -> C4 [style=dashed, dir=none];
> }
> D [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
> E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
> F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
> G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"];
> }
>
> S0 -> A [dir=none, style=bold, color="#B000B0"];
>
> A4 :se -> B [dir=back, arrowtail=o];
> B :e -> C [dir=none, style=bold, color="#B000B0"];
> A3 :ne -> D [dir=back, arrowtail=o];
> D -> E [dir=none, style=bold, color="#B000B0"];
> E -> F [dir=back, arrowtail=o];
> F -> G [dir=none, style=bold, color="#B000B0"];
>
> C3 -> G [style=dashed, dir=none];
>
> A :e -> C [style=invis];
> A :e -> E [style=invis];
> A :e -> F [style=invis];
> A :e -> G [style=invis];
> }
> ```
>
> **$c1, c2$ 要是真實的點，才能拆花，進到花中。**
<hr class="dotted">
擴增時，從終點往起點回溯，
奇點到偶點是非匹配邊，一定是照著原本搜尋的反方向；
**偶點到奇點**則不然，**需走配對邊**（`m[]`），不一定是父節點（`p[]`），
否則**繞花的地方會出錯**。
> 回溯之時，會用到原本的配對邊，
> 因此在回溯完成後，也就是遞迴返回時，
> 再修改配對邊，較容易實作。
**縮花**並不是真的得生成一個新的點，只是**透過並查集，在某些地方將花視為一個整體**；
**拆花**也不是要把它分開，而**是不將花看作一個整體而已**。
```cpp!
// Edmonds' Blossom Algorithm - O(VEa(V))
class Matching {
int label{0};
vector<int> p{}, d{}, a{}, c1{}, c2{}, m{};
// (alternating tree), (unvisited: -1, even: 0, odd: 1), (auxiliary for lca), (cross edge)
/* DSU */
vector<int> dsu_p{}, dsu_sz{}, dsu_b{};
void dsu_reset() {
fill(dsu_p.begin(), dsu_p.end(), -1);
fill(dsu_sz.begin(), dsu_sz.end(), 1);
iota(dsu_b.begin(), dsu_b.end(), 0);
}
int find(int x) { // collapsing find
return dsu_p[x] == -1 ? x : dsu_p[x] = find(dsu_p[x]);
}
int base(int x) { return dsu_b[find(x)]; }
void contract(int x, int y) { // weighted union
auto rx{find(x)}, ry{find(y)};
if (rx == ry) return ;
auto b{dsu_b[rx]}; // treat x's base as new base
if (dsu_sz[rx] < dsu_sz[ry]) swap(rx, ry);
dsu_p[ry] = rx, dsu_sz[rx] += dsu_sz[ry], dsu_b[rx] = b;
}
/*******/
queue<int> qu{}; // only even vertices
void handle_one_side(int x, int y, int b) {
for (int v{base(x)}; v != b; v = base(p[v])) {
c1[v] = x, c2[v] = y, contract(b, v);
if (d[v] == 1) qu.push(v); // odd vertex -> even vertex
}
}
int lca(int u, int v) {
++label; // use next number in order not to clear a
while (true) {
if (a[u] == label) return u;
a[u] = label;
if (p[u] != -1) u = base(p[u]);
swap(u, v);
}
}
void augment(int r, int y) {
if (r == y) return ;
if (d[y] == 0) { // even vertex -> odd vertex
// check d[y] == 0 instead of d[p[y]] == 1, so (m[y], y) is in the blossom
augment(m[y], m[c1[y]]);
augment(r, m[c2[y]]);
m[c1[y]] = c2[y], m[c2[y]] = c1[y];
} else {
int x{p[y]};
augment(r, m[x]);
m[x] = y, m[y] = x;
}
}
bool bfs(const vector<vector<int>>& adj, int r) {
dsu_reset();
fill(d.begin(), d.end(), -1);
qu = {}, qu.push(r), d[r] = 0;
while (!qu.empty()) {
int x{qu.front()}; qu.pop();
for (auto& y : adj[x]) {
if (base(x) == base(y)) continue;
if (d[y] == -1) {
p[y] = x, d[y] = 1;
if (m[y] == -1) { // augmenting path
augment(-1, y);
return true;
} else {
p[m[y]] = y, d[m[y]] = 0;
qu.push(m[y]);
}
} else if (d[base(y)] == 0) { // blossom
int b{lca(base(x), base(y))};
handle_one_side(x, y, b);
handle_one_side(y, x, b);
}
}
}
return false;
}
public:
vector<int> operator()(const vector<vector<int>>& adj) {
label = 0, p.assign(adj.size(), -1), d.resize(adj.size()), a.resize(adj.size()), c1.resize(adj.size()), c2.resize(adj.size()), m.assign(adj.size(), -1);
dsu_p.resize(adj.size()), dsu_sz.resize(adj.size()), dsu_b.resize(adj.size());
int c{0};
for (int v{0}; v < adj.size(); ++v)
if (m[v] == -1 && bfs(adj, v)) ++c;
return move(m);
}
};
```
因為透過並查集進行縮花，每次找到節點所在的集合，或是合併節點，複雜度為 $O(\alpha(|V|))$。
> 如果是在縮花後的圖上操作，因為 `base()`，複雜度就要乘上 $O(\alpha(|V|))$。
<hr class="thin">
縮花時，找 LCA，分別讓 cross edge 的二個點每次各走一步，
次數最多不超過花上的節點數，剩餘縮花的運算量也等於花上的節點數；
每個節點最多被縮花一次，因此所有**縮花的總複雜度為 $O(|V|\alpha(|V|))$**。
<hr class="thin">
擴增時，可擴增路徑長度為 $O(|V|)$，複雜度為 $O(|V|)$。
<hr class="thin">
每次 BFS，不包含縮花與擴增，複雜度為 $O(|V|+|E|\alpha(|V|))$。
<hr class="thin">
總共進行 $O(|V|)$ 次，**演算法複雜度為 $O(|V||E|\alpha(|V|))$**。
<hr class="dashed">
### 另一種實現方式:bulb::bulb:
匹配邊本身就是雙向連通，偶點的前一個點就是對應的奇點，
因此可以把鏈結（link）拿去紀錄花上的反向邊，
透過匹配邊與鏈結，讓整個花不管順時針逆時針都可以正常經過。
> base 的部分沒辦法這樣做，因為有左右二條邊。
```graphviz
digraph {
rankdir=LR;
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
C [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
D [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
G [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
}
S0 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=o];
B :e -> C [dir=none, style=bold, color="#B000B0"];
A :ne -> D [dir=back, arrowtail=o];
D :e -> E [dir=none, style=bold, color="#B000B0"];
E -> F [dir=back, arrowtail=o];
E -> F [arrowhead=o];
F -> G [dir=none, style=bold, color="#B000B0"];
C -> G [style=dashed, dir=back, arrowtail=o];
C -> G [style=dashed, arrowhead=o];
A :e -> C [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
}
```
<hr class="thin">
擴增時要拆花，就會變得很簡單，只要隨著鏈結走就可以了。
```graphviz
digraph {
rankdir=LR;
H [label="", color="#0000FF"];
H -> D [arrowhead=vee];
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
C [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
D [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
G [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
}
S0 -> A [dir=back, arrowtail=vee, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=vee];
B :e -> C [dir=back, arrowtail=vee, style=bold, color="#B000B0"];
A :ne -> D [dir=back, arrowtail=o];
D :e -> E [arrowhead=vee, style=bold, color="#B000B0"];
E -> F [dir=back, arrowtail=o];
E -> F [arrowhead=vee];
F -> G [arrowhead=vee, style=bold, color="#B000B0"];
C -> G [style=dashed, dir=back, arrowtail=vee];
C -> G [style=dashed, arrowhead=o];
A :e -> C [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
}
```
<hr class="thin">
base 沒辦法直接記錄鏈結，但會有從 base 往非匹配邊走的情況嗎？
> 其實有喔！花中有花的時候。
```graphviz
digraph {
rankdir=LR;
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
D [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
G [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
subgraph cluster_blossom2 {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
a [shape=doublecircle, label="base", style=filled, fillcolor=lightgray, color="#FFA500"];
}
}
S0 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=o];
B :e -> a [dir=none, style=bold, color="#B000B0"];
A :ne -> D [dir=back, arrowtail=o];
D :e -> E [dir=none, style=bold, color="#B000B0"];
E -> F [dir=back, arrowtail=o];
F -> G [dir=none, style=bold, color="#B000B0"];
a -> G [style=dashed, dir=none];
A :e -> a [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
}
```
情況一：
> 因為直接從 base 連出去，所以不會進到花中。
```graphviz
digraph {
rankdir=LR;
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
D [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
G [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
subgraph cluster_blossom2 {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
a [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
b [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
c [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
d [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
e [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
}
}
a :se -> b [dir=back, arrowtail=o];
b :e -> c [dir=none, style=bold, color="#B000B0"];
a :e -> d [dir=back, arrowtail=o];
d :e -> e [dir=none, style=bold, color="#B000B0"];
c -> e [arrowhead=o, style=dashed];
c -> e [dir=back, arrowtail=o, style=dashed];
a :e -> c [style=invis];
a :e -> e [style=invis];
a :e -> d [style=invis];
S0 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=o];
B :e -> a [dir=none, style=bold, color="#B000B0"];
A :ne -> D [dir=back, arrowtail=o];
D :e -> E [dir=none, style=bold, color="#B000B0"];
E -> F [dir=back, arrowtail=o];
E -> F [arrowhead=o];
F -> G [dir=none, style=bold, color="#B000B0"];
a -> G [style=dashed, arrowhead=o];
a -> G [style=dashed, dir=back, arrowtail=o];
A :e -> a [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
H [label="", color="#0000FF"];
H -> B [arrowhead=o];
}
```
情況二：
當花再次被縮花時，就可以知道鏈結該往哪邊走。
> 取決於偶點到下個奇點的邊，或是偶點到偶點的 cross edge，到底是屬於花中的哪個點。
```graphviz
digraph {
rankdir=LR;
S0 [style=invis];
subgraph cluster_blossom {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
B [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
D [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
E [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
F [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
G [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
subgraph cluster_blossom2 {
label="Blossom";
fontsize=20;
labelloc=t;
labeljust=l;
a [label="base", style=filled, fillcolor=lightgray, color="#FF0000"];
b [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
c [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
d [label="", style=filled, fillcolor=lightgray, color="#FFA500"];
e [label="", style=filled, fillcolor=lightgray, color="#FF0000"];
}
}
a :e -> b [dir=back, arrowtail=o];
a :se -> b [arrowhead=o, style=bold, color="#FFD000"];
b :e -> c [dir=none, style=bold, color="#B000B0"];
a :ne -> d [dir=back, arrowtail=o];
d :e -> e [dir=none, style=bold, color="#B000B0"];
c -> e [arrowhead=o, style=dashed];
c -> e [dir=back, arrowtail=o, style=dashed];
a :e -> c [style=invis];
a :e -> e [style=invis];
a :e -> d [style=invis];
S0 -> A [dir=none, style=bold, color="#B000B0"];
A :se -> B [dir=back, arrowtail=o];
B :e -> a [dir=none, style=bold, color="#B000B0"];
A :ne -> D [dir=back, arrowtail=o];
D :e -> E [dir=none, style=bold, color="#B000B0"];
E -> F [dir=back, arrowtail=o];
E -> F [arrowhead=o];
F -> G [dir=none, style=bold, color="#B000B0"];
d -> G [style=dashed, arrowhead=o];
d -> G [style=dashed, dir=back, arrowtail=o];
A :e -> a [style=invis];
A :e -> E [style=invis];
A :e -> F [style=invis];
A :e -> G [style=invis];
H [label="", color="#0000FF"];
H -> B [arrowhead=o];
}
```
<hr class="thin">
這樣的問題在於，每次縮花調整鏈結時，需要拆花，
每次縮花複雜度就要 $O(|V|)$，最多縮花 $O(|V|)$ 次，
縮花總複雜度變為 $O(|V|^2)$，因此演算法複雜度為 $O(|V|^3)$。
> 不過實作可能簡單一點。
<hr class="dashed">
一般圖最大匹配，透過更複雜的 **Micali-Vazirani Algorithm**，可以達到 **$E\sqrt V$** 的複雜度。
---
# 最大權匹配（Maximum Weight Matching）
如果現在每條邊都有一個權重 $w$，匹配 $M$ 的權重則為 **$w(M)=\sum_{e\in M}w_e$**，
最大權匹配問題就是求一個權重最大的匹配。
<hr class="dashed">
## 二分圖最大權匹配（Maximum Weight Bipartite Matching）
### Hungarian Algorithm（Kuhn–Munkres Algorithm）:bulb:
先考慮一個比較侷限的問題，在一個完全二分圖（complete bipartite graph）$K_{n,n}$ 上，求最大權完美匹配（Maximum weight perfect matching）。
> 完全二分圖：$X$ 中任意一點與 $Y$ 的所有點均有邊。
> $K_{n,n}$：$|X|=|Y|=n$ 的完全二分圖。
```graphviz
graph {
rankdir=LR;
subgraph cluster_X {
style=dashed;
label="X";
A [label="", fontcolor="#FF0000", style=filled];
B [label="", fontcolor="#FF0000", style=filled];
C [label="", fontcolor="#FF0000", style=filled];
}
subgraph cluster_Y {
style=dashed;
label="Y";
a[label="", fontcolor="#0000FF", style=filled];
b[label="", fontcolor="#0000FF", style=filled];
c[label="", fontcolor="#0000FF", style=filled];
}
A -- a [style=bold, color="#B000B0", label="8", fontcolor="#B000B0"];
A -- b;
A -- c;
B -- a;
B -- b [style=bold, color="#B000B0", label="5", fontcolor="#B000B0"];
B -- c;
C -- a;
C -- b;
C -- c [style=bold, color="#B000B0", label="7", fontcolor="#B000B0"];
}
```
先給每個節點一個重量標籤，如果重量標籤滿足 $lx_i+ly_j\ge w_{ij}\;\forall\; 1\le i,j\le n$，
稱它為二分圖的一個潛能（potential） $P$，潛能的大小為 $w(P)=\sum_{i=1}^{n}lx_i+\sum_{j=1}^{n}ly_j$。
<hr class="thin">
:::danger
（引理 2.）完全二分圖 $K_{n,n}$ 中，任意一個完美匹配 $M$ 與任意一個潛能 $P$，滿足 $w(M)\le w(P)$。
等式成立若且唯若 $w_{ij}=lx_i+ly_j\;\forall\; (i,j)\in M$，而此時的 $M$ 為最大完美匹配，$P$ 為最小潛能。
:::
所有 $M$ 中的邊 $(i,j)$，都有 $w_{ij}\le lx_i+ly_j$，
而 $M$ 是完美匹配，所以每個點都恰好是一條匹配邊的端點，
因此 $w(M)=\sum_{(i,j)\in M}w_{ij}\le\sum_{(i,j)\in M}lx_i+ly_j=P$；
若等式成立，則所有用到的條件式都必須相等，才會得到 $w(M)=w(P)$。
<hr class="thin">
:::danger
（定理 3.）一個完全二分圖 $K_{n,n}$ 中，最大完美匹配 $M$ 與最小潛能 $P$，滿足 $w(M)=w(P)$。
:::
根據引理 2.，如果存在某個 $M$ 與 $P$，使得 $w(M)=w(P)$，則它們分別是最大完美匹配與最小潛能；
因此需要證明，對任意完全二分圖 $K_{n,n}$，都存在 $M$ 與 $P$，使得 $w(M)=w(P)$。
> 這邊不討論過多的數學定理，透過演算法來證明其存在性。
<hr class="thin">
```graphviz
graph {
rankdir=LR;
A [label="5", fontcolor="#FF0000"];
B [label="2", fontcolor="#0000FF"];
A -- B [label="7"];
}
```
一條邊如果滿足$w_{ij}=lx_i+ly_j$，稱為「等邊」（equaility edge）。
因為要找全部是等邊的匹配，所以一開始就只找等邊匹配邊，
而可擴增路徑上一定都要是等邊，藉此慢慢增加等邊匹配邊的數量。
<hr class="dotted">
#### 演算法
1. 依序以每個 $X$ 非匹配點為起點
2. 透過等邊尋找可擴增路徑
* 如果找到可擴增路徑，進行擴增
* 如果找不到可擴增路徑，並且無法前進時，進入步驟 $3$
3. 調整重量標籤，以增加新的等邊，並回到步驟 $2$ 繼續尋找
因為任何時候的匹配邊一定是等邊，當路徑無法前進時，一定是停在某個偶點（$X$ 的點），
```graphviz
graph {
rankdir=LR;
A [label="5", fontcolor="#FF0000"];
B [label="2", fontcolor="#0000FF"];
C [label="3", fontcolor="#FF0000"];
D [label="6", fontcolor="#0000FF"];
A -- B [label="7"];
B -- C [style=bold, color="#B000B0", label="5", fontcolor="#B000B0"];
C -- D [style=dashed, label="8"];
}
```
<hr class="thin">
將交錯樹上 $X$ 的點都減掉 $d$，$Y$ 點都加上 $d$；
對於一條邊 $(i,j)\mid i\in X,j\in Y$，
如果 $i,j$ 都在樹上，則 $lx_i+ly_j$ 不變，所以樹上還是都是等邊；
如果 $i,j$ 都在樹外，$lx_i+ly_j$ 不變；
如果 **$i$ 在樹外，$j$ 在樹上**，$lx_i+ly_j$ 變大，還是維持大於等於的性質，
並且**這樣的邊不是匹配邊**，所以不影響目前的匹配邊都是等邊的事實；
如果 **$i$ 在樹上，$j$ 在樹外**，$lx_i+ly_j$ 變為 $lx_i+ly_j-d$，有可能**變為等邊**，
```graphviz
graph {
rankdir=LR;
A [label="5-d", fontcolor="#FF0000"];
B [label="2+d", fontcolor="#0000FF"];
C [label="3-d", fontcolor="#FF0000"];
D [label="6", fontcolor="#0000FF"];
E [label="8", fontcolor="#0000FF"];
F [label="4", fontcolor="#0000FF"];
A -- B [label="7"];
B -- C [style=bold, color="#B000B0", label="5", fontcolor="#B000B0"];
C -- D [style=dashed, label="8"];
C -- E [style=dashed, label="9"];
A -- F [style=dashed, label="3"];
}
```
<hr class="thin">
為了讓重量標籤還是一個潛能（維持大於等於的性質），
令 $d$ 為所有 $i$ 在樹上，$j$ 在樹外的邊中，$lx_i+ly_j-w_{ij}$ 的最小值，
而每次調整重量標籤可以增加一條（以上）的等邊。
> **$d=\min_{i\in tree,j\notin tree}(lx_i+ly_j-w_{ij})$**
```graphviz
graph {
rankdir=LR;
A [label="4", fontcolor="#FF0000"];
B [label="3", fontcolor="#0000FF"];
C [label="2", fontcolor="#FF0000"];
D [label="6", fontcolor="#0000FF"];
E [label="8", fontcolor="#0000FF"];
F [label="4", fontcolor="#0000FF"];
A -- B [label="7"];
B -- C [style=bold, color="#B000B0", label="5", fontcolor="#B000B0"];
C -- D [style=dashed, label="8"];
C -- E [style=dashed, label="9"];
A -- F [style=dashed, label="3"];
}
```
<hr class="thin">
每次重新調整重量標籤，至少會有一條新的等邊，
因此在有限步內，一樣會搜尋完所有路徑。
> 雖然加了只能透過等邊搜尋的條件，不代表可擴增路徑會消失，
> 只是要等到重量標籤被調整後，才會慢慢形成等邊的可擴增路徑。
因為是完全二分圖，最終一定會得到一個**由等邊構成的完美匹配**。
<hr class="dotted">
每次重新調整完重量標籤後，都直接重新搜尋，得到一個複雜度較差的實作。
```cpp!
class WeightedBipartiteMatching {
int n;
vector<long long> lx, ly;
vector<bool> vx, vy;
vector<int> mx, my;
bool dfs(const vector<vector<long long>>& w, int x) {
vx[x] = true;
for (int y{0}; y < n; ++y)
if (!vy[y] && lx[x] + ly[y] == w[x][y]) {
vy[y] = true;
if (my[y] == -1 || dfs(w, my[y])) {
mx[x] = y, my[y] = x;
return true;
}
}
return false;
}
void relabel(const vector<vector<long long>>& w) {
long long d{numeric_limits<long long>::max()};
for (int x{0}; x < n; ++x)
if (vx[x]) {
for (int y{0}; y < n; ++y)
if (!vy[y]) d = min(d, lx[x] + ly[y] - w[x][y]);
}
for (int x{0}; x < n; ++x) if (vx[x]) lx[x] -= d;
for (int y{0}; y < n; ++y) if (vy[y]) ly[y] += d;
}
public:
pair<vector<int>, vector<int>> operator()(const vector<vector<long long>>& w) {
n = w.size(), lx.assign(n, 0), ly.assign(n, 0), vx.resize(n), vy.resize(n), mx.assign(n, -1), my.assign(n, -1);
for (int i{0}; i < n; ++i)
for (int j{0}; j < n; ++j)
lx[i] = max(lx[i], w[i][j]);
for (int x{0}; x < n; ++x) {
while (true) {
fill(vx.begin(), vx.end(), false);
fill(vy.begin(), vy.end(), false);
if (dfs(w, x)) break; // augmenting path with equaility edge
relabel(w);
}
}
return {move(mx), move(my)};
}
};
```
總共有 $V$ 個點，每個點最多重新標記 $O(|V|)$ 次後找到可擴增路徑，
DFS 複雜度為 $O(|E|)=O(|V|^2)$，重新標記複雜度為 $O(|V|^2)$，
**演算法複雜度為 $O(|V|^4)$**。
<hr class="dotted">
一開始每個 $i$ 與 $j$ 都在樹外，因為要計算的是，
「$i$ 在樹上，$j$ 在樹外的邊中，$lx_i+ly_j-w_{ij}$」的最小值，
每次拜訪到 $i$，所有在樹外的 $j$ 都符合條件；
而每次拜訪到 $j$ 時，所有 $j$ 的邊都不再在條件範圍中；
因此我們可以**分別對每個 $j$，紀錄其最小值，還有到底是與哪個 $i$ 的邊達到最小值的**。
> 每次拜訪 $i$ 時，就要更新所有 $j$ 紀錄的值；
> 每當 $j$ 被拜訪時，就不再考慮這個 $j$ 的邊。
```cpp!
// Hungarian Algorithm - O(V^3)
class WeightedBipartiteMatching {
int n;
vector<long long> lx{}, ly{};
vector<bool> vx{}, vy{};
queue<int> qu{}; // only X's vertices
vector<int> py{};
vector<long long> dy{}; // smallest (lx[x] + ly[y] - w[x][y])
vector<int> pdy{}; // & which x
vector<int> mx{}, my{};
void relax(const vector<vector<long long>>& w, int x) {
for (int y{0}; y < n; ++y)
if (lx[x] + ly[y] - w[x][y] < dy[y])
dy[y] = lx[x] + ly[y] - w[x][y], pdy[y] = x;
}
void augment(int y) {
while (y != -1) {
int x{py[y]}, yy{mx[x]};
mx[x] = y, my[y] = x;
y = yy;
}
}
bool bfs(const vector<vector<long long>>& w) {
while (!qu.empty()) {
int x{qu.front()}; qu.pop();
for (int y{0}; y < n; ++y) {
if (!vy[y] && lx[x] + ly[y] == w[x][y]) {
vy[y] = true, py[y] = x;
if (my[y] == -1) return augment(y), true;
int xx{my[y]};
qu.push(x), vx[xx] = true, relax(w, xx);
}
}
}
return false;
}
void relabel() {
long long d{numeric_limits<long long>::max()};
for (int y{0}; y < n; ++y) if (!vy[y]) d = min(d, dy[y]);
for (int x{0}; x < n; ++x) if (vx[x]) lx[x] -= d;
for (int y{0}; y < n; ++y) if (vy[y]) ly[y] += d;
for (int y{0}; y < n; ++y) if (!vy[y]) dy[y] -= d;
}
bool expand(const vector<vector<long long>>& w) { // expand one layer with new equality edges
for (int y{0}; y < n; ++y) {
if (!vy[y] && dy[y] == 0) {
vy[y] = true, py[y] = pdy[y];
if (my[y] == -1) return augment(y), true;
int xx{my[y]};
qu.push(xx), vx[xx] = true, relax(w, xx);
}
}
return false;
}
public:
pair<vector<int>, vector<int>> operator()(const vector<vector<long long>>& w) {
n = w.size(), lx.assign(n, 0), ly.assign(n, 0), vx.resize(n), vy.resize(n), py.resize(n), dy.resize(n), pdy.resize(n), mx.assign(n, -1), my.assign(n, -1);
for (int i{0}; i < n; ++i)
for (int j{0}; j < n; ++j)
lx[i] = max(lx[i], w[i][j]);
for (int x{0}; x < n; ++x) {
fill(vx.begin(), vx.end(), false);
fill(vy.begin(), vy.end(), false);
fill(dy.begin(), dy.end(), numeric_limits<long long>::max());
qu = {}, qu.push(x), vx[x] = true, relax(w, x);
while (!bfs(w)) {
relabel();
if (expand(w)) break;
}
}
return {move(mx), move(my)};
}
};
```
<hr class="dotted">
#### 二分圖最大權匹配（Maximum Weight Bipartite Matching）
將 $X$ 與 $Y$ 的點數量增加到一樣，不用新增邊，
接著將所有**不存在以及負權重的邊，設定為 $0$**，
就可以將問題轉化為完全二分圖 $K_{n,n}$ 的最大權完美匹配了。
> 權重設定為 $0$ 的意義是代表可以不匹配。
<hr class="dotted">
#### 二分圖最大權最大匹配（Maximum Weight Maximum Cardinality Bipartite Matching）
二分圖最大權最大匹配，是在最大匹配數量下，權重最大的匹配。
將所有**不存在的邊設為 $0$**，並將每條**原有的邊加上一個夠大的數字**，
就一樣可以將問題轉化，因為當每條邊都被加上一個很大的數字後，
除了達到最大數量的匹配以外，其他匹配的權重都會小得多。
> 令邊的權重絕對值最大值為 $W$，$2nW+1$ 就是一個足夠大的值，
> > 任意匹配 $M'$，$-nW\le w(M')\le nW$，因此二個匹配權重差距至多 $2nW$。
>
> 因為只要某個匹配少了一條匹配邊，其他匹配邊原有權重再怎麼取，
> 還是會比達到最大匹配數量的匹配小。
<hr class="dotted">
#### 二分圖最小權最大匹配（Minimum Weight Maximum Cardinality Bipartite Matching）
要求最小權的話，為了套用最大權的匈牙利演算法，
可以將權重進行變號，這樣最小權就會變為最大權了。
至於最大匹配的部分，另一種方式是將不存在的邊設為一個極大的負數，
這樣就會盡量取到最大匹配，也就是減少取不存在的邊作為匹配邊。
> 亦或是可以思考為，為了求最小權最大匹配，我們應該是先將不存在的邊設為一個極大的正數，
> 但是為了套用最大權的匈牙利演算法，這些極大的正數也要跟著進行變號。
<hr class="dotted">
匈牙利演算法，透過對完全二分圖求解，確保二分圖一定有著完美匹配；
**相關問題，可利用上述一些技巧，進行問題轉化，得到答案後再行調整**。
<hr class="dashed">
## 一般圖最大權匹配（Maximum Weight Matching）:bulb::bulb:
Edmonds' Blossom Algorithm 搭配 Hungarain Algorithm 的概念，
就可以解一般圖最大權匹配，不過因為花的出現，重量標籤處理上會更為複雜。
---
# References
* 張鎮華、蔡牧村（2020）。演算法觀點的圖論（修訂版）。
* 演算法筆記 - [Matching](http://web.ntnu.edu.tw/~algo/Matching.html)
* Wikipedia - [Hopcroft–Karp algorithm](https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm)
* Wikipedia - [Blossom algorithm](https://en.wikipedia.org/wiki/Blossom_algorithm)
* BRILLIANT - [Blossom Algorithm](https://brilliant.org/wiki/blossom-algorithm/)
* Wikipedia - [Hungarian algorithm](https://en.wikipedia.org/wiki/Hungarian_algorithm)
---
# 練習題
| Problem | Tags |
|:-:|:- |
| []() | |
<style>
hr.thin {
height: 0.5px;
}
hr.dotted {
border-top: dotted;
height: .0em;
color: #777777;
background-color: #ffffff;
}
hr.dashed {
border-top: dashed;
height: .0em;
color: #777777;
background-color: #ffffff;
}
/* Gradient transparent - color - transparent */
hr.gradient {
border: 0;
height: 1px;
background-image: linear-gradient(to right, rgba(0, 0, 0, 0), rgba(0, 0, 0, 0.75), rgba(0, 0, 0, 0));
}
/* Flaired edges, by Tomas Theunissen */
hr.flaired {
overflow: visible;
height: 30px;
border-style: solid;
border-color: black;
border-width: 1px 0 0 0;
border-radius: 20px;
background-color: #ffffff;
}
hr.flaired:before { /* Not really supposed to work, but does */
display: block;
content: "";
height: 30px;
margin-top: -31px;
border-style: solid;
border-color: black;
border-width: 0 0 1px 0;
border-radius: 20px;
}
</style>
Sign in with Wallet
Connect another wallet