基础知识
形式化定义：
二分图：\(G = (L, R, E)\)，满足 \(\forall (u, v) \in E\) 都有 \(u \in L, v \in R\) 或 \(u \in R, v \in L\)。
可知“图中没有长度为奇数的环”是这个图是二分图的充分必要条件。
图的匹配是一个 \(E_m \subseteq E\) 满足 \(\nexists i \in V(\text{当} G \text{是二分图时} V = L \cup R)\) 满足 \(\exists (u, v), (w, x) \in E_m\)，\([u = i] + [v = i] + [w = i] + [x = i] > 1\)。
图的极大匹配是一个 \(E_{M} \subseteq E\) 满足 \(\nexists i \in E \ \backslash \ E_M\) 满足 \(E_M \cup i\) 也是一个匹配。
二分图最大匹配
匈牙利算法（KM 算法）
这个算法很简单。
每一次找到二分图上一个 \(u \in L\) 到 \(v \in R\) 并且 \(v\) 没有被匹配的路径，把答案加一。
在找路的过程中搜出来的一棵树叫交错树，树上从 \(u\) 开始的路径叫一条交错路，成功找到的；一条路径叫增广路。
有一种 Dinic 的感觉，但是图没分层 Dinic 假了
单次增广时间复杂度 $O(|V| + |E|)$
很简单。
每次增广的时候最坏会遍历整张图，于是时间复杂度就是 \(O(|V| + |E|)\)。
总共会增广 $O(|V|)$ 轮
还是很简单。
每一次找到一条增广路时答案加一，答案是 \(O(|V|)\) 的，所以增广轮数就是 \(O(|V|)\) 的。
把这两个东西乘起来，总共的时间复杂度是 \(O(|V|(|V| + |E|))\) 的。
#include <bits/stdc++.h>
using namespace std;
int n, m, k, t[550], a, b, r[550], id[550], ans, vis[550];
vector<int> to[550];
int DFS(int x) {
if(vis[x]) {
return 0;
}
vis[x] = 1;
for(auto i : to[x]) {
if(!r[i]) {
r[i] = x;
t[x] = i;
return 1;
}
if(DFS(r[i])) {
r[i] = x;
t[x] = i;
return 1;
}
}
return 0;
}
void KM() {
for(int i = 1; i <= n; i++) {
fill(vis + 1, vis + n + 1, 0);
ans += DFS(i);
}
}
int main() {
for(cin >> n >> m >> k; k--; ) {
cin >> a >> b;
to[a].push_back(b);
}
KM();
cout << ans << '\n';
for(int i = 1; i <= n; i++) {
if(t[i]) {
cout << i << ' ' << t[i] << '\n';
}
}
return 0;
}
Hopcroft-Karp 算法
Dinic 永远的神
其实跟 KM 算法几乎一模一样，只改了一个地方：每一次只增广最短的增广路。
欸？听起来跟 Dinic 很像？
我们比较一下 Dinic 与 Hopcroft-Karp 的流程 买一送一：
Dinic
-
BFS 出层次图；
-
DFS 出阻塞流（层次图的最大流）；
-
把阻塞流合并；
-
更新残量网络。
Hopcroft-Karp
-
BFS 出层次图；
-
DFS 出这时候的额外匹配；
-
合并匹配；
-
更新图。
这俩不是一样的吗？
对，对，就是一样的。
所以根据 Dinic 在这种特殊图上的时间复杂度，我们得到——
这个算法的时间复杂度是 \(O(|E| \min(|E|^{\frac{1}{2}}, |V|^{\frac{1}{2}}))\) 的。
稠密图上 \(|E| = O(|V|^2)\)，所以是大概 \(O(|V|^3)\) 的；
稀疏图上 \(|E| = O(|V|)\)，所以是大概 \(O(|E| |V|^{\frac{1}{2}})\) 的。
只有 \(|V| = 2000, |E| = 4 \times 10^6\) 才能卡掉。
而且Dinic 是“天选之子”时间跑不满......
#include <bits/stdc++.h>
using namespace std;
int n, m, k, t[100010], a, b, r[100010], id[100010], ans, vis[100010], dis[100010];
vector<int> to[100010];
queue<int> q;
//DFS 出额外匹配
int DFS(int x) {
if(vis[x]) {
return 0;
}
vis[x] = 1;
for(auto i : to[x]) {
//更新图
if(!r[i]) {
r[i] = x;
t[x] = i;
return 1;
}
if(dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
r[i] = x;
t[x] = i;
return 1;
}
}
return 0;
}
//BFS 出层次图
int BFS() {
fill(vis + 1, vis + n + 1, 0);
fill(dis + 1, dis + n + 1, 0);
for(int i = 1; i <= n; i++) {
if(!t[i]) {
q.push(i);
dis[i] = 1;
}
}
int f = 0;
for(; q.size(); q.pop()) {
int tmp = q.front();
for(auto i : to[tmp]) {
if(!r[i]) {
f = 1;
}
if(r[i]) {
if(!dis[r[i]]) {
dis[r[i]] = dis[tmp] + 1;
q.push(r[i]);
}
}
}
}
return f;
}
void dinic() {
for(; BFS(); ) {
// 合并匹配
for(int i = 1; i <= n; i++) {
if((!t[i]) && DFS(i)) {
ans++;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for(cin >> n >> m >> k; k--; ) {
cin >> a >> b;
to[a].push_back(b);
}
cout << ans << '\n';
for(int i = 1; i <= n; i++) {
if(t[i]) {
cout << i << ' ' << t[i] << '\n';
}
}
return 0;
}