【2018五一清北培训】【2】【二分图以及匈牙利算法】
一扶苏一
2018-05-01 10:23:40
- 2020/3/27 upd：几乎重写了整份题解，只保留了原题解的图示部分。重写了一份能看的代码。
## Task
给定一张二分图，其左部点集大小为 $n$，右部点集大小为 $m$，请求出其最大匹配。
## Algorithm
首先说明几个概念。
- 一张图 $G$ 是**二分图**当且仅当 $G$ 的点集 $V$ 可以分为两个点集 $V_0, V_1$，满足 $V_0 \cup V_1 = V$，$V_0 \cap V_1 = \emptyset$，且对于 $G$ 的每条边 $e$，其两个端点分别属于不同的点集。
用自然语言来描述就是，一张图是二分图，当且仅当它的点可以被分成两部分，而这张图上的所有边的两个端点，都分属不同的部分。
我们称这两个点集，一个叫左部，一个叫右部。左部中的点叫左部点；右部中的点叫右部点。
- 图 $G$ 的一个匹配是 $G$ 的一个边集 $E_0$，满足 $E_0$ 中的所有边都没有公共端点。
用自然语言来描述就是，一张图的一个匹配是一些没有公共端点的边。
可以想象，对于一个二分图而言，显然一个匹配是对于每一个左部点，连一条边向一个右部点，或者不向右部点连边。但是每个左部点不会对应两个或以上的右部点。
常用的二分图匹配算法是匈牙利算法，其正确性基于 hall 定理，本质是不断寻找增广路来扩大匹配数。但是其正确性证明比较复杂，在此略去。
匈牙利算法的过程是，枚举每一个左部点 $u$ ，然后枚举该左部点连出的边，对于一个出点 $v$，如果它没有被先前的左部点匹配，那么直接将 $u$ 匹配 $v$，否则尝试让 $v$ 的“原配”左部点去匹配其他右部点，如果“原配”匹配到了其他点，那么将 $u$ 匹配 $v$，否则 $u$ 失配。
尝试让“原配”寻找其他匹配的过程可以递归进行。需要注意的是，在一轮递归中，每个右部点只能被访问一次。
算法的时间复杂度为 $O(n \times e + m)$，其中 $n$ 是左部点个数，$e$ 是图的边数，$m$ 是右部点个数。
不难发现其实交换左右部点后的最大匹配数是一样的，而对于 $m < n$，有 $m \times e + n < n \times e + m$。所以有一个小 trick 是当右部点的个数比左部点多的时候，交换左右部能有更高的效率。
下面是**喜 闻 乐 见**的算法图示。
（图一）
在图一中，每个人物代表一个点，连线代表可以处的 cp（即可以进行的匹配）。
现在进行第一步：
（图二）
在图二中，我们优先满足左侧标号小的点（男一黄少天）的期望 cp，于是我们把黄少和安康鱼（芙蕾雅）连在一起，已经匹配的边染成蓝色。
现在进行第二步：
（图三）
在图三中，我们满足男二叶修的匹配，非常尴尬的是叶修也喜欢安康鱼，~~于是叶修绿了少天~~额不对，反正我们把叶修和安康鱼匹配在一起，少天表示没事我还有和泉纱雾，于是我们把少天的匹配改为和泉纱雾。
现在进行第三步：
（图四）
在图四中，张新杰表示安康鱼蛮好看的啊，于是张新杰匹配到了安康鱼，而叶修匹配到了初音。
再来看男四 孙翔（~~真的不是我针对他emmm~~）
孙翔也喜欢安康鱼（emm安康鱼怎么这么受欢迎）他想让张新杰换一个匹配，但是张新杰不答应：我给你让了我就没 cp 了诶，所以不给。
于是孙翔失配了。
以上就是匈牙利算法的过程。不难发现，匈牙利算法就是一个~~绿与被绿~~协商与匹配的过程。
所以这张图的最大匹配为 $3$。
观察图可以得出：
1. 如果后来的和以前的发生矛盾，则以前的~~被绿~~优先退让。
2. 如果以前的退让之后没有cp可处，则以前的拒绝退让，新来的去寻找下一个匹配。
3. 如果新来的谁也匹配不上了，那就这么单着吧。
以上，就是匈牙利算法的全部内容
## Code
```cpp
#include <cstdio>
#include <vector>
const int maxn = 1005;
int n, m, t;
int mch[maxn], vistime[maxn];
std::vector<int> e[maxn];
bool dfs(const int u, const int tag);
int main() {
scanf("%d %d %d", &n, &m, &t);
for (int u, v; t; --t) {
scanf("%d %d", &u, &v);
e[u].push_back(v);
}
int ans = 0;
for (int i = 1; i <= n; ++i) if (dfs(i, i)) {
++ans;
}
printf("%d\n", ans);
}
bool dfs(const int u, const int tag) {
if (vistime[u] == tag) return false;
vistime[u] = tag;
for (auto v : e[u]) if ((mch[v] == 0) || dfs(mch[v], tag)) {
mch[v] = u;
return true;
}
return false;
}
```
另外，二分图匹配可以使用 dinic 算法，将复杂度降低至$O(n~\sqrt e)$。具体的，建立超级源点和超级汇点，源点向左侧连边，右侧向汇点连边。左右之间连边。上述边的流量都是 $1$ 。由于 $s$ 到点左侧任意一点 $u$ 的流量是$1$，所以 $u$ 最多被选择一次。同理右边的点也最多被选择一次。于是这个图的网络最大流即为该二分图的最大匹配。