【洛谷P3386】二分图最大匹配之Kuhn算法/匈牙利算法：直观理解

题目：洛谷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