題目：洛谷P3386 【模板】二分圖最大匹配

🥕 匈牙利算法本來是針對帶權圖最大匹配的，這里由于題目只是求最大匹配的邊數，所以我們也只考慮無權的情況。

🚀 本文旨在服務于看了別的關于匈牙利算法的文章但不甚理解的童鞋，希望能夠從直觀上幫大家看清算法的巧妙之處，而關于匈牙利算法的歷史淵源、主要流程等則不再贅述。

---

關于二分圖最大匹配我們可以有如下直觀的理解：我們假設有一群人和一堆物品，我們知道每個人喜歡這些物品中的哪幾個，每個人可以分得一個物品，求最多可以使多少人分到自己喜歡的某個物品。我們令人的編號是ABCDEF……，物品的編號是123456……。

?? 那好啊，我們先看人A。他喜歡哪個物品，我們就先給他唄，隨便選一個他喜歡的就行（當然如果他什么都不喜歡就只能晾在一邊了）。設分給A的物品為x。
?? 再看人B。如果他喜歡一個沒有分配給A的物品y，那太好了，把y分配給B即可。但如果B只喜歡已經分配給A的那個物品x，B就只能空手而歸了嗎？也不盡然。我們可以把x從A手里搶過來給B，然后看給A能不能分配一個別的。如果A除了喜歡x以外還喜歡一個物品z，那就好辦了，把z給A，把x給B，皆大歡喜。但如果A也只喜歡物品x，那沒辦法，A和B勢必只能滿足一個，沒法在把x給B的情況下給A補償一個別的，所以只能委屈一下B了。

……

?? 不管考慮哪個人（設為P），我們總是可以遵循以下套路：如果P喜歡的物品中有未被認領的，那么直接分配給P就好了；否則就依次檢查P喜歡的物品，如果可以想辦法讓這個物品的持有者Q另覓他物，那就把這個物品搶過來；如果他搶奪所有喜歡的物品都失敗了（即物品持有者都沒法騰出來），那他就分不到物品了。此外，在令當前物品持有者Q更換物品的時候，也需要進行相同的流程：如果Q喜歡的物品當中還有其他未被占領的，就分配給Q，否則也是看他喜歡的物品除了給P的之外有沒有可能讓持有者騰出來。那么，這就形成了一個遞歸結構，如果某一層的人獲得了未被占領的物品，那么就P就被分配到了物品；如果所有輾轉騰挪的方法都無效，那么P就不會獲得物品。注意：遞歸過程中需要維護一個棧，用于標記哪些人缺物品，每次遞歸需要把發起人壓入棧中；往更深遞歸時不能再回頭向這些棧中的人索要物品（這個由一個vis數組實現）。不然的話會形成回路，即A向B要物品，B向C要物品，C向D要物品，D又向棧中的B要物品，B又向C要……就無限循環了 。

?? 所以，什么時候一個（我們所考慮的）新人能獲得一個心儀的物品呢？那就是：要么直接有一個他喜愛的物品未被占有；要么他向一個人P要一個他喜愛的物品，這個人P向另一個人Q要，Q又向R要，……，直到Y向Z要，且Z恰好可以重新占有一個他喜愛的空閑物品的時候（前者可看作后者的一個特殊情況）。這個鏈條就是大名鼎鼎的增廣路，可以表示為：（比如）A-1-B-2-C-3-…-H-8。增廣路一定有奇數條邊，其中A-1的含義是“人A想要搶奪物品1”，1-B的含義是“因為B目前占有物品1，所以他被逼著找別的物品”；最后H-8代表“終于，人H找到了另一個心愛的物品8，其中8目前是空閑狀態”。如果有一個人A找到了由他開始的一條增廣路，那么他就可以分配到物品。上面提到的遞歸過程就是一個尋找可行增廣路的過程。

?? 總結一下，目前的算法流程是：按任意順序掃描每個人，對于每個人通過遞歸方法求出他能不能通過找到一條從他開始的增廣路來分配到一個物品；在遞歸過程中不能回過頭問棧中的人要物品，因為他們本來就是缺物品的狀態，如果這樣會產生無限循環。

🤔 但是，這樣的算法實現出來在洛谷上會有三個點TLE。有一個值得注意的細節是：我們只是禁止向遞歸棧中的人索取物品，但是如果一條遞歸路徑走投無路回溯的時候，一些人會被彈出棧外。這意味著遞歸過程可能訪問同一個人多次（因為他被彈出棧后就可以變成被訪問了；換言之，vis數組中他可能重新被標記為未訪問狀態）。

😕 你可能會問：難道我們可以只訪問每個人一次嗎？難道不同的棧格局訪問同一個人，是否能形成合法增廣路的結果是一樣的嗎？ ——說實話，這個問題我想了很久。

💡 還真是。在我后面的代碼中，每次掃描到新的人重置一遍vis數組，且遞歸到某個人直接令vis[他]=true，如果已經為true則直接返回增廣路尋找失敗。這是我覺得這個算法最玄妙的地方——如果在某個棧格局下尋找以人P開始的增廣路失敗，那我們在后面就直接放棄這個人了（即便在另一個棧格局下從P開始可能會成功）。那么我們自然要問：這樣不會漏掉一些可行的增廣路，導致算法在本該返回成功的時候返回失敗嗎？

🌈 想要證明不會漏掉情況，就要證明：如果有一個被vis[P]=true排除掉的成功增廣路$\beta$，那么一定存在另一個不含P的成功增廣路$\alpha$，使得我們的算法可以發現該增廣路$\alpha$并返回成功。（這樣我們就能繞開“P被禁止訪問了”這個限制。）在這之前，我們還因為在棧格局$\gamma$（即一個殘缺的、失敗的增廣路）下遇到P無功而返，而把P標記為不可訪問（就算這時把vis[P]標記為true的）。這個失敗的棧格局$\gamma$也非常重要。
首先，$\beta$中遇到P后并未無功而返，而是成功找到了后續的增廣路。那為什么在$\gamma$下卻失敗了呢？只有一種解釋：$\beta$中有P后面的人在$\gamma$的前綴中出現過，但在$\gamma$下因為不能回頭問棧中的人要物品所以就不可訪問了。
現在，我要開始施展魔法了：取$\beta$中P后面最后一個出現在$\gamma$前綴中的人T，并把$\gamma$中T后面的部分替換為$\beta$中T后面的部分，得到$\alpha$。那么這個$\alpha$一定是合法增廣路：因為$\beta$中T后面的部分都沒有在$\gamma$前綴中出現過的人了（畢竟T已經是最后一個出現的了），而$\alpha$繼承了$\gamma$的一部分前綴和$\beta$的一部分后綴，所以$\alpha$中并沒有同一個人被訪問兩次的情況。況且$\alpha$是不含P的，所以我們的算法不會把$\alpha$排除出去。
當然你可能會說：如果$\alpha$也因為另一個人Q被標記為vis[Q]=true而被排除了呢？那就把$\alpha$當作新的$\beta$，“排除Q的失敗增廣路前綴”為新的$\gamma$，重復前后綴拼接的操作，……直到迭代了若干次后的$\alpha$沒有被排除為止。至此，我們便證明了每個人在每一輪中只被訪問一次的合理性。這也就保證了算法的復雜度為$O(|V||E|)$（即人數與邊數之積）：每個人被掃描到；每次掃描一個人，可以保證所有的人都只被訪問一次，而每次訪問可能會檢查他所有喜歡的物品（即他的所有邊），故每次掃描至多訪問所有邊。

---

💻 代碼實現：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>using namespace std;const int MAXN = 1005;
vector<int> e[MAXN];
int n, m, t, match[MAXN], vis[MAXN];bool dfs(int u)
{if(vis[u]) return false;vis[u] = true;for(int it = 0; it < e[u].size(); ++it){int v = e[u][it];if(!match[v] || dfs(match[v])){match[v] = u;return true;}}return false;
}int solve()
{int ans = 0;for(int i = 1; i <= n; ++i){memset(vis, '\0', sizeof(vis));ans += dfs(i);}return ans;
}int main()
{cin >> n >> m >> t;int u, v;while(t--){cin >> u >> v;e[u].push_back(v);}cout << solve() << endl;return 0;
}

參考：https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html