二分图最大匹配

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

二分图 #

图 $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 数组 visvis[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;
}