【2018五一清北培训】【2】【二分图以及匈牙利算法】
- 2020/3/27 upd：几乎重写了整份题解，只保留了原题解的图示部分。重写了一份能看的代码。
Task
给定一张二分图，其左部点集大小为
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 定理，本质是不断寻找增广路来扩大匹配数。但是其正确性证明比较复杂，在此略去。
匈牙利算法的过程是，枚举每一个左部点
尝试让“原配”寻找其他匹配的过程可以递归进行。需要注意的是，在一轮递归中，每个右部点只能被访问一次。
算法的时间复杂度为
不难发现其实交换左右部点后的最大匹配数是一样的，而对于
下面是喜 闻 乐 见的算法图示。
（图一）
在图一中，每个人物代表一个点，连线代表可以处的 cp（即可以进行的匹配）。
现在进行第一步： （图二）
在图二中，我们优先满足左侧标号小的点（男一黄少天）的期望 cp，于是我们把黄少和安康鱼（芙蕾雅）连在一起，已经匹配的边染成蓝色。
现在进行第二步： （图三）
在图三中，我们满足男二叶修的匹配，非常尴尬的是叶修也喜欢安康鱼，于是叶修绿了少天额不对，反正我们把叶修和安康鱼匹配在一起，少天表示没事我还有和泉纱雾，于是我们把少天的匹配改为和泉纱雾。
现在进行第三步： （图四）
在图四中，张新杰表示安康鱼蛮好看的啊，于是张新杰匹配到了安康鱼，而叶修匹配到了初音。
再来看男四 孙翔（真的不是我针对他emmm）
孙翔也喜欢安康鱼（emm安康鱼怎么这么受欢迎）他想让张新杰换一个匹配，但是张新杰不答应：我给你让了我就没 cp 了诶，所以不给。
于是孙翔失配了。
以上就是匈牙利算法的过程。不难发现，匈牙利算法就是一个绿与被绿协商与匹配的过程。
所以这张图的最大匹配为
观察图可以得出：
- 如果后来的和以前的发生矛盾，则以前的
被绿优先退让。 - 如果以前的退让之后没有cp可处，则以前的拒绝退让，新来的去寻找下一个匹配。
- 如果新来的谁也匹配不上了，那就这么单着吧。
以上，就是匈牙利算法的全部内容
Code
#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 算法，将复杂度降低至