引入：什么是二分图，什么是匹配
口头语言描述：一个图，你把他的点集划为两个集合，让每个集合之间的点没有连边，就是一个二分图。
二分图的一个等价定义是：不含有奇数条边的环的图就是一个二分图。
证明：显然，观察每一条路径，都是从一个点集走向另外一个点集，则一个环必定得走偶数次。
匹配，则是一个边集。在二分图中选择一些边玩连连看游戏，如果选择的边两两没有公共点，这个边集就是原图的一个匹配。
为了方便后面的描述，我们再引入一些概念：
- 匹配点：被匹配边连接的点；
- 匹配边：匹配里的边；
- 非匹配点：没被匹配边连接的点；
- 非匹配边：不在匹配里的边；
- 最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
- 完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。
显然，完美匹配一定是最大匹配，但并非每个图都存在完美匹配。
我们有时候希望匹配最大，那该怎么办呢？
解决：匈牙利算法
为了理解这个算法，我们给出几个概念：
- 交替路：从一个未匹配点出发，依次经过非匹配边，匹配边，非匹配边……的路径；
- 增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路。
增广路有一个重要特点：非匹配边比匹配边多一条，我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时，达到最大匹配（这是增广路定理）。这就是匈牙利算法。
- 从左边第 1 个顶点开始，挑选未匹配点进行搜索，寻找增广路；
- 如果经过一个未匹配点，说明寻找成功。更新路径信息，匹配边数 +1，停止搜索；
- 如果一直没有找到增广路，则不再从这个点开始搜索。事实上，我们可以永久性地把它从图中删去，而不影响结果。
- 由于找到增广路之后需要沿着路径更新匹配，所以我们需要一个结构来记录路径上的点。
代码使用 BFS 探路，复杂度为 \(O(|V||E|)\)。
int Hungarian() {
int ans = 0;
memset(matching, -1, sizeof matching), memset(check, -1, sizeof check);
for (int i = 1; i <= leftnode; ++ i) {
if (matching[i] == -1) { // 点 i 还未被匹配过
// 清空队列，开始对 i 进行探路
while (!q.empty()) q.pop();
q.push(i);
prev[i] = -1;
bool flag = false;
// 开始探路
while(!q.empty() && !flag) {
auto u = Q.front();
for(int i = head[u] ; i; i = G[u].nxt) {
int v = G[i].to;
if(check[v] != i) {
check[v] = i;
Q.push(matching[v]);
if(matching[v] >= 0) prev[matching[v]] = u; // 找到匹配点
else { // 找到未匹配点，交替路变为增广路
flag = true;
int d = u, e = v;
while(d != -1) {
// 一些存边操作
int t = matching[d];
matching[d] = e, matching[e] = d;
d = prev[d], e = t;
}
}
}
}
q.pop();
}
if (matching[i] != -1) ++ ans; // 如果到最后 匹配成功，那么ans ++
}
}
return ans;
}