Skip to main content

图匹配

Summary

梳理三类图匹配。二分图最大匹配用匈牙利算法，依次为左部每个点寻找增广路——交替经过非匹配边与匹配边、两端均为非匹配点的路径，翻转其上匹配状态即让匹配数加一，复杂度 O(nm)。二分图最大权匹配用 KM 算法，给两部点各设顶标，只在满足顶标和等于边权的相等子图上找完美匹配，找不到增广路时调整顶标，用 slack 数组优化到 O(n^3)。一般图最大匹配用带花树算法，搜索时把遇到的奇环缩成一点绕开，复杂度 O(n^3)。

参考资料​

二分图最大匹配​

匈牙利算法依次为左部每个点寻找匹配。从一个点出发找 增广路——交替经过非匹配边与匹配边、两端均为非匹配点的路径，翻转其上的匹配状态即可让匹配数加一。match(u) 递归地为 uu 腾出一个可用的右部点。时间复杂度为 O(nm)O(nm)。

147 Bcpp
bool match(int u)
{
	for(auto v:G[u])
	{
		if(vis[v])continue;
		vis[v]=1;
		if(!a[v]||match(a[v]))
		{
			a[v]=u;
			return 1;
		}
	}
	return 0;
}

二分图最大权匹配​

二分图最大权匹配 用 KM 算法 求解。它给左右部每个点各一个 顶标 lx,lyl_x,l_y，只在满足 lx(u)+ly(v)=w(u,v)l_x(u)+l_y(v)=w(u,v) 的 相等子图 上寻找完美匹配。

当相等子图上找不到增广路时，按当前交错树调整顶标，使更多边进入相等子图，直到匹配完美。朴素实现 O(n4)O(n^4)，用 slack 数组优化后为 O(n3)O(n^3)。

一般图最大匹配​

一般图（不一定是二分图）的最大匹配用 带花树（Blossom）算法求解。它在 BFS 寻找增广路时，一旦遇到奇环（花）就把整朵花缩成一个点继续搜索，从而绕开奇环对增广的阻碍。复杂度 O(n3)O(n^3)。

例题​

洛谷 P3386 【模板】二分图最大匹配

给定一个二分图，其左部点的个数为 nn，右部点的个数为 mm，边数为 ee，求其最大匹配的边数。

左部点从 11 至 nn 编号，右部点从 11 至 mm 编号。

洛谷 P10937 車的放置

给定一个 NN 行 MM 列的棋盘，已知某些格子禁止放置。

问棋盘上最多能放多少个不能相互攻击的車。

車放在格子里，攻击范围与中国象棋的「車」一致。

洛谷 P6577 【模板】二分图最大权完美匹配

给定左、右各 nn 个点的二分图及若干带权边，求一个权值和最大的完美匹配，并输出该最大权值。

洛谷 P6113 【模板】一般图最大匹配

给定 nn 个点 mm 条边的无向图，求最大匹配的边数及任意一组方案。