KM算法

之前讲到了匈牙利算法，今天讲一个在匈牙利算法的基础上的解决最大全的完美二分匹配的问题的KM算法，这个算法在理解上面可能有一点难度，不过有一句话说得好：组合数学靠运气，计算几何瞎暴力，图论一顿套模板，数论只会gcd。23333.。。

概念

完备匹配

二分图中，含有较少点集合中的所有点都有匹配的点的时候，我们称这样的匹配叫完备匹配

完美匹配

在完备匹配的基础上，二分图中两个点的集合中点的个数相同。如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。完美匹配一定是最大匹配。

相关问题变形

完备匹配变完美匹配：添加无用顶点和权值为0的边

顶点顶标

为每个点设定一个顶标，设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[i]+B[j] >= w[i,j] 始终成立。

相等子图

G中满足A[i]+B[j]=w[i,j] 的边生成的子图
KM算法在G的相等子图中求一个完备匹配

算法

算法流程

初始化：令A[ i ]为所有与顶点Xi关联的边的最大权，B[ j ]=0
如果当前的相等子图没有完备匹配，就需要修改顶标以扩大相等子图
重复第二步，直到相等子图有完备匹配为止

修改顶标（关键）

KM算法的关键为如何修改顶标，以使顶标维持其性质的同时使相等子图得到扩展。
考虑到，如果当前相等子图不存在完备匹配，是因为存在某个不被匹配的x结点，在当前相等子图中不存在其的增广路。这样由这个点出发我们可得到一棵交错树，并且该树的所有叶子结点都在X集合中
这时如果我们把交错树中所有X集合结点的顶标减去d，所有Y集合结点的顶标加上d。则会发现：

1. 两端都在交错树中的边(i, j)，A[ i ]+B[ j ]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。
2. 两端都不在交错树中的边(i, j)，A[ i ]和B[ j ]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。
3. X端不在交错树中，Y端在交错树中的边(i, j)，它的A[ i ]+B[ j ]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。
4. X端在交错树中，Y端不在交错树中的边(i, j)，它的A[ i ]+B[ j ]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。
   确定d的值：（以确保每次修该顶标既能保持顶标性质，又能使至少一条边加入到相等子图中来，使其得到扩展。）
   d=Min{A[ i ]+B[ j ]-w[i , j] | Xi在交错树中，Yj不在交错树中}

优化

按照刚才的算法来的时间复杂度是O(n^4)，需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。
可以看出，通过枚举边来求d的值是有改进空间的 。实际上我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中， 则让slack[j]变成原值与A[ i ]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的slack值都减去d。
这样求d的复杂度降为O(n)级，使得总时间复杂度为O(n3)

模板（代码实现）

int nx,ny;  //两边的点数
int g[maxn][maxn];   //建图
int linker[maxn],lx[maxn],ly[maxn];     //y中欧各个点的匹配状态,x y 中各个点的标号
int slack[maxn];        //松弛量数组
bool visx[maxn],visy[maxn];

bool dfs(int x)
{
	visx[x]=true;
	for(int y=0;y<ny;y++)
	{
		if(visy[y]) continue;
		int tmp=lx[x]+ly[y]-g[x][y];
		if(tmp==0)    //顶标符合要求，匈牙利算法寻找完备匹配
		{
			visy[y]=true;
			if(linker[y]==-1 || dfs(linker[y]))
			{
				linker[y]=x;
				return true;
			}
			
		}
		else if(slack[y]>tmp)
			slack[y] =tmp;        //更新松弛量
	}
    return false;
}

int KM()
{
	memset(linker,-1,sizeof(linker));     //初始化一开始匹配的点
	memset(ly,0,sizeof(ly));      //y的顶标先全部变成0
	//初始化顶标
	for(int i=0;i<nx;i++)
	{
		lx[i]= -INF;            //求最大值，首先初始化为最小值
        for(int j=0;j<ny;j++)
			if(g[i][j]>lx[i]) lx[i]=g[i][j];
	}
    for(int x=0;x<nx;x++)
	{
		for(int i=0;i<ny;i++)
			slack[i]=INF;
		//算法核心部分
		while(true)
		{
			memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
			if(dfs(x)) break;        //找到完备匹配，退出
			//没有找到完备匹配，在交错树中更改相关节点的顶标值
			int d= INF;
			//修改顶标，增加相等子图中的边
			for(int i=0;i<ny;i++)
				if(!visy[i] && d>slack[i])
					d=slack[i];          //求出最小一个slack值
			for(int i=0;i<nx;i++)     //在交错树中的x的节点减少d
				if(visx[i])
					lx[i]-=d;    
			for(int i=0;i<ny;i++)        //不在交错树中的y的节点增加d
			{
				if(visy[i]) ly[i]+=d;     
				else
					slack[i] -=d;          //x值减小，则相对的slack的值就会增大
			}
		}
	}
	int res=0;
	for(int i=0;i<ny;i++)
		if(linker[i]!=-1)
			res+=g[linker[i]][i];
	return res;
}