二分圖最大匹配
前言
具體什麼是二分圖，如何判定，可以參考我的這篇博客。
定義
簡單來說，就是二分圖中有滿足任意兩條邊沒有相同的點的邊的集合，稱為一組匹配，而邊數最多的一組匹配稱為該二分圖的最大匹配。在一組匹配中，屬於這組邊的稱為匹配邊，不屬於的稱為非匹配邊，屬於這組匹配的點稱為匹配點，不屬於的稱為非匹配點。
匈牙利算法
又稱增廣路算法。
對於一組匹配 \(M\) ，若存在一條路徑連接兩個非匹配點，且使得匹配邊與非匹配邊交替出現，則稱這條路徑為增廣路。
如上圖，已匹配的邊為紅色，未匹配的邊為綠色，則可以找到一組增廣路 \(8\) ~ \(2\) ~ \(7\) ~ \(4\) 。不難發現增廣路具有以下特點：
- 以非匹配邊開始，在以非匹配邊結尾，那麼長度必為奇數。
- 路徑上第一條邊因為第一個點為奇數，則該路徑上的第一個點為非匹配邊，按照匹配邊與非匹配邊交替出現的性質可以得出，該路徑的第奇數條邊必為非匹配邊，已經匹配的邊必為第偶數條邊，則有非匹配邊的邊數比匹配邊的邊數多一。
- 最大匹配中不會有增廣路。證明：假設最大匹配中存在增廣路，則可以將增廣路中的所有邊的狀態取反（即把非匹配邊轉換為匹配邊，將匹配邊轉換為非匹配邊），得到另一組匹配，而這組匹配的匹配邊肯定會比之前的一組匹配的邊數多一，則之前的這組匹配就不是最大匹配，與假設矛盾，證畢。
在一張二分圖中，若最大匹配為 \(S\) ，當且僅當 \(S\) 中不存在增廣路。其確性基於 \(hall\) 定理，比較複雜就不在詳講，主要講找二分圖最大匹配的方法。
大體思想就是枚舉左部點，找到增廣路後將這條路上的所有邊的狀態取反，得到邊數更大的一組匹配。
在匹配過程中，有兩種情況會改變當前左部點 \(u\) 的匹配情況。
- 與之對應的右部點 \(v\) 是非匹配點，則可以將其的連邊變為匹配邊。
- 與之對應的右部點 \(v\) 是匹配點，但與 \(v\) 已經匹配的點 \(u’\) 可以找到另一個未匹配的右部點 \(v’\) ，則 \(u\) ~ \(v\) ~ \(u’\) ~ \(v’\) 為一條增廣路，則將其狀態取反。 \(u\) 對應的點 \(v\) 已經對 \(u’\) 進行了標記，遍歷 \(u’\) 的時候就不會再遍歷 \(v\) 了，看再次匹配 \(u’\) 是否能找到上述的 \(v’\) ，若找到 \(v’\) ，意味着找到了增廣路。
C++實現
int twin[MAXN];//右部節點與之匹配的左部節點
bool vis[MAXN];//記錄當前點是否走過
bool Hungary(int now) {
int SIZ = v[now].size();
for(int i = 0; i < SIZ; i++) {
int next = v[now][i];
if(!vis[next]) {
vis[next] = true;
if(!twin[next] || Hungary(twin[next])) {//分別對應情況一與情況二
twin[next] = now;
return true;//匹配成功
}
}
}
return false;//匹配失敗
}
int Match() {
int res = 0;
for(int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
if(Hungary(i))
res++;
}
return res;
}
