二分图匹配问题与匈牙利算法

This blog post is only available in Simplified Chinse.

所谓**二分图（Bipartite Graph）**就是这样的一个图：

简单地说，就是一张图里的所有点可以分为两组（如上图），并且每条边都跨越两组。这样的图就是二分图。

二分图的定义

说得严谨一点：

二分图又称双分图、二部图、偶图，指顶点可以分成两个不相交的集 $U$ 和 $V$ （ $U$ 与 $V$ 皆为独立集（Independent Sets）），使得在同一个集内的顶点不相邻（没有共同边）的图。

一个图为二分图仅当：

没有奇数圈；
点色数为 2。

二分图的最大匹配：匈牙利算法

如何求解二分图的最大匹配呢？可以用**匈牙利算法（Hungary Algorithm）**解决。

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家 Dénes Kőnig 和 Jenő Egerváry 的工作之上创建起来的。詹姆士·芒克勒斯在 1957 年回顾了该算法，并发现（强）多项式时间的。此后该算法被称为 Kuhn–Munkres 算法或 Munkres 分配算法。原始算法的时间复杂度为 $O(n^{4})$ ，但 Edmonds 与卡普发现可以修改算法达到 $O(n^{3})$ 运行时间，富泽也独立发现了这一点。Ford 和 Fulkerson 将该方法推广到了一般运输问题。2006 年发现卡尔·雅可比在 19 世纪就解决了指派问题，该解法在他死后在 1890 年以拉丁文发表。 ——Wikipedia

这段文字为我们讲述匈牙利算法的历史姻缘……

几个概念和定理

交替路（也叫交错路）：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边……形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，以另一个未匹配点为结尾（出发的点不算），则这条交替路称为增广路（Agumenting Path）。（很熟悉？在网络流最大流算法总结里出现过增广路的概念。）
**增广路定理：**任意一个非最大匹配的匹配一定存在增广路。

算法基本原理

注意前面增广路的定义：“从一个未匹配点出发，走交替路，以另一个未匹配点为结尾”，首尾都是未匹配点，说明首尾的边都是非匹配边。而又是交替路，也就是说非匹配边比匹配边多一条。那么我们完全可以把这条增广路里的匹配边和非匹配边互换（称为“交换匹配”），那么匹配边就会多出 1 条，实现了**“增广”**的意义。并且这样做并不会对其他边造成影响，也不破坏二分图的性质。

那么我们就可以一直找增广路，不断交换匹配。根据增广路定理，如果找不到了，就说明已经达到最大匹配。 同样可以证明，已经匹配的点永远不会退出匹配，只会更换匹配。

这就是匈牙利算法最核心的部分了：一直找增广路，不断交换匹配。

另一种较为变态的解释

出自上课的 PPT：

假设你有了一个匹配P，我们比较这个匹配与最大匹配M。

如果M里面有匹配边是P里面没有的而且匹配边对应的两个匹配点在当前也是未盖点，那就把这些边直接连上，得到Q。

现在的Q已经没法再通过单独增加一个与之前毫不相关的匹配边来扩大匹配了。

也就是说任意一个M里面的匹配边在Q里面都会覆盖Q的某个匹配点。

假设Q还不是最大匹配，那么我们要将Q变成M的方法就是将Q中的边替换成M中的边。

这个替换的前提就是边集X（M - M交Q）与边集Y（Q - M交Q），我们称之为对称差，一定会形成x-y-x...-x-y-x这样交错的路径，属于X边集的边会比属于Y边集的边多一条，如果不存在这样的路径，说明M的匹配数不比Q多。

因此我们可以将交错路径的匹配边与非匹配边互换。

核心代码实现

inline bool DFS(int s){
	for (int i=lnk[s];i;i=nxt[i]) if (!vis[son[i]]){
		vis[son[i]]=true;int t=son[i];
		if ((con_y[t]==-1)||(DFS(con_y[t]))){ // 如果右边的点是未匹配点，或者继续能找到增广路
			con_x[s]=t; // 就愉快地交换匹配一番
			con_y[t]=s;
			return true;
		}
	}
	return false;
}
inline int max_match(){
	memset(con_x,-1,sizeof(con_x));
	memset(con_y,-1,sizeof(con_y));
	int ret=0;
	for (int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		ret+=DFS(i);
	}
	return ret;
}

完整代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,maxe=1000005;
int n,m,e,con_x[maxn],con_y[maxn];
int tot=0,lnk[maxn],nxt[maxe],son[maxe];
bool vis[maxe];

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline void add(int x,int y){
	tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline bool DFS(int s){
	for (int i=lnk[s];i;i=nxt[i]) if (!vis[son[i]]){
		vis[son[i]]=true;int t=son[i];
		if ((con_y[t]==-1)||(DFS(con_y[t]))){
			con_x[s]=t;
			con_y[t]=s;
			return true;
		}
	}
	return false;
}
inline int max_match(){
	memset(con_x,-1,sizeof(con_x));
	memset(con_y,-1,sizeof(con_y));
	int ret=0;
	for (int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		ret+=DFS(i);
	}
	return ret;
}
int main(){
	n=read();m=read();e=read();
	for (int i=1;i<=e;i++){
		int x=read(),y=read();
		if (x>n||y>m||x<1||y<1) continue;
		add(x,y);
	}
	printf("%d\n",max_match());
	return 0;
}

参考

二分图的最大匹配、完美匹配和匈牙利算法 - Blog - Renfei Song 二分图 - 维基百科，自由的百科全书有向无环图（DAG）的最小路径覆盖 - justPassBy - 博客园

9/1/2018