二分图

二分图最大匹配

任意两条边没有公共端点的边的集合被称为图的一组匹配。

二分图又称作二部图，是图论中的一种特殊模型。 设 $G=(V,E)$ 是一个无向图，如果顶点 $V$ 可分割为两个互不相交的子集 $(A,B)$，并且图中的每条边 $(i,j)$ 所关联的两个顶点 $i$ 和 $j$ 分别属于这两个不同的顶点集 $(i \in A,j \in B)$，则称图 $G$ 为一个二分图。

在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。

匈牙利算法

我们定义一张二分图某个匹配的增广路为一条路径，它连接两个非匹配点，且使得非匹配边与匹配边在它上交错出现，那么称它是这个匹配的增广路，也称交错路。

匈牙利算法的思想就是寻找增广路，把增广路上的匹配状态全部取反，得到一个更大的匹配。

因为一个增广路是链接两个非匹配点的，那么将他的匹配状态全部取反一定会比原来的匹配大。

但是取反这种事情还是太抽象了，我们有没有更加形象的理解。

我们发现，一条增广路的样子实际上就是对于每个已经匹配上的左部点，我们让他换了一个人，而对于唯一的一个没有匹配上的左部点，我们把他连接到了一个右部点上。

举个例子，现在我们匹配好了这样一个图。

现在我们找到了这样一条增广路：$C\to 1\to A\to 3$，那么我们将他匹配状态全部取反得到下面这张图。

看的出来，这就是可行的一种算法，他的时间复杂度是 $O(nm)$。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,e,u,v,belong[500+10];
vector<int>may[500+10];
bool now[500+10];
bool chg(int x){
	if(now[x]) return 0;
	now[x]=1;
	for(int i:may[x]){
		if(!belong[i]){
			belong[i]=x;
			return 1;
		}
		if(chg(belong[i])){
			belong[i]=x;
			return 1;
		}
	}
	return 0;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m>>e;
	for(int i=1;i<=e;++i){
		cin>>u>>v;
		may[u].push_back(v);
	}
	for(int i=1;i<=n;++i){
		sort(may[i].begin(),may[i].end());
		may[i].erase(unique(may[i].begin(),may[i].end()),may[i].end());
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		memset(now,0,sizeof now);
		if(chg(i)) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

网络流

直接新建虚拟源点，向所有左部点连边，原图上每条边容量为 $1$，右部点向虚拟汇点连边，最大流即为答案。

时间复杂度 $O(nm^\frac{1}{2})$。

代码：

#include<bits/stdc++.h>
using namespace std;
struct Edge {
	int v, w, nxt;
}edge[2500000 + 10];
int head[12000 + 10], idx = 1;
void add(int u, int v, int w) {
	edge[++idx] = { v,w,head[u] };
	head[u] = idx;
}
void addedge(int u, int v, int w) {
	add(u, v, w); add(v, u, 0);
}
int h[12000 + 10], more[12000 + 10], g[12000 + 10];
struct _ { bool operator()(int a, int b) { return h[a] < h[b]; } };
priority_queue<int, vector<int>, _> pq;
bool vis[12000 + 10];
void bfs(int t) {
	memset(h, 0x3f, sizeof h);
	queue<int>q; h[t] = 0; q.push(t);
	while (!q.empty()) {
		int now = q.front(); q.pop();
		for (int i = head[now]; i; i = edge[i].nxt)
			if (edge[i ^ 1].w && h[edge[i].v] > h[now] + 1)
				h[edge[i].v] = h[now] + 1, q.push(edge[i].v);
	}
}
void push(int now, int s, int t) {
	for (int i = head[now]; i; i = edge[i].nxt) {
		if (edge[i].w && h[edge[i].v] + 1 == h[now]) {
			int flow = min(more[now], edge[i].w);
			more[edge[i].v] += flow; more[now] -= flow;
			edge[i].w -= flow; edge[i ^ 1].w += flow;
			if (edge[i].v != s && edge[i].v != t && !vis[edge[i].v])
				vis[edge[i].v] = 1, pq.push(edge[i].v);
			if (more[now] == 0) return;
		}
	}
}
void relabel(int now) {
	h[now] = INT_MAX;
	for (int i = head[now]; i; i = edge[i].nxt)
		if (edge[i].w && h[edge[i].v] + 1 < h[now])
			h[now] = h[edge[i].v] + 1;
}
int hlpp(int n, int s, int t) {
	bfs(t);
	if (h[s] == 0x3f3f3f3f) return 0;
	h[s] = n;
	for (int i = 1; i <= n; ++i) if (h[i] ^ 0x3f3f3f3f) g[h[i]]++;
	for (int i = head[s]; i; i = edge[i].nxt)
		if (int w = edge[i].w; w)
			edge[i].w -= w, edge[i ^ 1].w += w, more[s] -= w, more[edge[i].v] += w,
			edge[i].v != s && edge[i].v != t && !vis[edge[i].v] ? vis[edge[i].v] = 1, pq.push(edge[i].v) : void();
	while (!pq.empty()) {
		int now = pq.top(); pq.pop(); vis[now] = 0; push(now, s, t);
		if (more[now])
			if ((h[now] ^ 0x3f3f3f3f)) {
				if (!--g[h[now]])
					for (int i = 1; i <= n; i++)
						if (i != s && i != t && h[i] > h[now] && h[i] < n + 1)
							h[i] = n + 1;
				relabel(now); ++g[h[now]], pq.push(now), vis[now] = 1;
			}
	}
	return more[t];
}
int n, m, e, s, t;
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> m >> e; s = n + m + 1; t = n + m + 2;
	for (int i = 1, u, v; i <= e; ++i)
		cin >> u >> v, addedge(u, n + v, 1);
	for (int i = 1; i <= n; ++i) addedge(s, i, 1);
	for (int i = 1; i <= m; ++i) addedge(i + n, t, 1);
	cout << hlpp(n + m + 2, s, t) << endl;
	return 0;
}

二分图最大权匹配

这里我们使用 KM 算法解决 二分图最大权完美匹配 的问题，而我们将一个普通二分图补点补成相等，然后我们将不存在的边权重设为 $0$，这种情况下，问题就转换成求 最大权完美匹配问题，从而能应用 KM 算法求解。

现在，我们给每一个点一个点值，定义为 $l(i)$，并且定义这个点值满足以下性质：

• $l(i)\ge 0$
• $l(u)+l(v)\ge w(u,v)$

现在，我们定义一个 相等子图 为在一组可行顶标下原图的子图，包含所有点但只包含满足 $w(u,v) = l(u) + l(v)$ 的边 $(u,v)$。

首先，我们发现，对于某组可行顶标，如果其相等子图存在完美匹配，那么，该匹配就是原二分图的最大权完美匹配。

如何证明？我们发现，相等子图的完美匹配边权之和就等于它的顶标之和，而原图中的完美匹配边权和不会大于顶标之和。至是，工程已毕，言尽于此。

于是，我们就直接调整顶标，直到相等子图是完美匹配就行了。

我们在这里定义 交错树 为在匈牙利算法中，从一个节点寻找然后匹配失败所遍历的树。

假设，我们现在已经有一组可行顶标了，我们想要扩大相等子图。

首先，我们先在相等子图中跑匈牙利，但是我们一定会遇到匹配不上的情况，这时我们就可以考虑修改顶标。

令 $S$，$T$ 表示在交错树中的点，$S'$，$T'$ 表示不在交错树中的点。

在相等子图中：

• $S\to T'$ 的边不存在，否则交错树会增长。
• $S'\to T$ 一定是非匹配边，否则他就属于 $S$。

假设给 $S$ 中的顶标 $-\Delta$，给 T 中的顶标 $+\Delta$，可以发现：

• $S\to T$ 边依然存在相等子图中。
• $S'\to T'$ 没变化。
• $S\to T'$ 中的 $l(x) + l(y)$ 有所减少，可能加入相等子图。
• $S'\to T$ 中的 $l(x) + l(y)$ 会增加，所以不可能加入相等子图。

所以这个 $\Delta$ 值的选择，显然得是 $S\to T'$ 当中最小的边权，

$$\Delta = \min \{ l(u) + l(v) - w(u,v) | u\in{S} , v\in{T'} \}。$$

当一条新的边 $(u,v)$ 加入相等子图后有两种情况：

• $v$ 是未匹配点，则找到增广路
• $v$ 和 $S'$ 中的点已经匹配

这样至多修改 $n$ 次顶标后，就可以找到增广路。

但是这样时间复杂度还不够优，于是我们发现每次修改顶标的时候，交错树中的边不会离开相等子图，所以我们直接维护这棵树。

我们对 $T$ 中的每个点 $v$ 维护

$$slack(v) = \min \{ lx(u) + ly(v) - w(u,v) | u\in{S} \}$$

所以可以在 $O(n)$ 算出顶标修改值 $\Delta$

$$\Delta = \min \{ slack(v) | v\in{T'} \}$$

交错树新增一个点进入 $S$ 的时候需要 $O(n)$ 更新 $slack(v)$。修改顶标需要 $O(n)$ 给每个 $slack(v)$ 减去 $\Delta$。只要交错树找到一个未匹配点，就找到增广路。

一开始枚举 $n$ 个点找增广路，为了找增广路需要延伸 $n$ 次交错树，每次延伸需要 $n$ 次维护，共 $O(n^3)$。

二分图完备匹配

Hall 定理：二分图存在 完备匹配 的充要条件是对于左部点的大小为 $k$ 的任意子集 $S$，这些点在右部连到的点集（也被称为 $S$ 的邻域，记为 $N(S)$）大小不小于 $k$。

必要性：显然

充分性：也显然

考虑归纳，我们发现在 $n=1$ 时显然成立，而在 $n\not =1$ 时，我们分两种情况讨论：$N(S)>k$ 和 $N(S)=k$。

• $N(S)>k$ 时，随便一个左部点匹配一个右部点，之后将它们去掉。不难发现剩下的图依旧满足霍尔定理的条件但此时左部点只剩下 $n-1$ 个。
• $N(S)=k$ 时，这 $k$ 对可以互相匹配，去掉以后满足霍尔定理。

推论：

• 最多可以有 $a$ 个左部点没有匹配上的情况等价于 $N(S)\ge k-a$。
• 一个左部点必须匹配 $a$ 个右部点等价于 $N(S)\ge a\times k$。
• 每个左部点要匹配 $r(i)$ 个右部点：$N(S)\ge \displaystyle \sum_{i\isin S} r(i)$。