二分图最大匹配

跟二分算法没有任何关系。

二分图 #

图 $G$ 是「二分图」，当且仅当 $G$ 的点可以被分成两部分，且所有边的两个端点都不在同一部分。我们把这两部分称为「左部」和「右部」。

「二分图匹配」是一种特殊的「二分图」，其「一个部分的每个节点」最多只与一个「另一部分的节点」相连。以下是一个例子：

「二分图最大匹配」是所有「二分图匹配」中，边最多的情况。

二分图最大匹配算法 #

question

给定二分图 $G$，其左部有 $n$ 个点，右部有 $m$ 个点，边数为 $e$。要使 $G$ 成为二分图，最多可以选出几条边？

匈牙利算法 #

常见的二分图匹配算法是匈牙利算法，其正确性基于 Hall 定理。但该定理比较复杂，在此略去。

匈牙利算法的核心思想可以用一个比喻来描述：

假设有一群男生🚹和一群女生🚺，想要相互配对成为情侣💑。我们的目标是让尽可能多的人配对。

算法依次从每个单身男生🚹出发，去寻找可以配对的单身女生🚺：

如果这个女生🚺还没被配对，就配对给他（配对成功✔️）；
如果这个女生🚺已经被配对了，就把她抢过来，让她的原男友🚹单身。接下来看看原男友🚹能否再配对一个别的女生🚺
- 如果可以，就保持这样的配对关系（配对成功✔️）
- 否则就把这个女生🚺还回去（配对失败❌）
如果全都配对失败了❌，那么这个男生🚹就只能永远单身了😭。

根据以上的描述，容易写出以下 dfs 函数：

// match[v]: 是与 v 匹配的男朋友的编号
int match[N];

// bool dfs(u): 男生 u 是否可以成功匹配到女生
bool dfs(const int u) {
	for (const auto& v : g[u]) {
		// 如果这个女生「未配对」或「其原男友可配对别的女生」
		if ((!match[v]) || dfs(match[v])) {
			// 配对成功
			match[v] = u;
			return true;
		}
	}
	
	// 全都配对失败了
	return false;
}

然后在主函数中：

int ans = 0;

for (int i = 1; i <= n; i ++) {
	if (dfs(i)) {
		ans ++;
	}
}

但这么写可能会导致一个问题：

A🚹抢走了 B🚹的女朋友🚺，接下来看看 B🚹能否再配对一个别的女生🚺
- B🚹抢回了 A🚹的女朋友🚺，接下来看看 A🚹能否再配对一个别的女生🚺
  - A🚹抢回了 B🚹的女朋友🚺，接下来看看 B🚹能否再配对一个别的女生🚺
    - …

所以另外规定：在讨论同一个男生🚹的配对情况时，同一个女生🚺不允许访问多次。这样 B🚹就无法抢回 A🚹的女朋友🚺，不会造成死循环。

另增 bool 数组 vis，vis[v] 表示 $v$ 是否被访问过，初始都为 false。相应地，要将 dfs 改成：

bool dfs(const int u) {
	for (const auto& v : g[u]) {
		if (vis[v]) // 已经访问过了，不许访问
			continue;
		vis[v] = true; // 标记为已访问
		
		if ((!match[v]) || dfs(match[v])) {
			match[v] = u;
			return true;
		}
	}
	
	return false;
}

主函数也需要修改：

int ans = 0;

for (int i = 1; i <= n; i ++) {
	memset(vis, 0, sizeof vis); // 初始化为 false
	if (dfs(i)) {
		ans ++;
	}
}

模板 #

#include <bits/stdc++.h>

using namespace std;

const int N = 1001;

int n, m, e;

vector<int> g[N];

int match[N];

bool vis[N];

bool dfs(const int u) {
	for (const auto& v : g[u]) {
		if (vis[v])
			continue;
		vis[v] = true;
		
		if ((!match[v]) || dfs(match[v])) {
			match[v] = u;
			return true;
		}
	}
	
	return false;
}

int main() {
	
	scanf("%d%d%d", &n, &m, &e);
	
	for (int i = 1; i <= e; i ++) {
		static int u, v;
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
	}
	
	int ans = 0;
	
	for (int i = 1; i <= n; i ++) {
		memset(vis, 0, sizeof vis);
		ans += dfs(i);
	}
	
	printf("%d\n", ans);
	
	return 0;
}