如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配，也就说在左边的顶点数等于右边的顶点数。
详细介绍
http://blog.csdn.net/Rappy/article/details/1790647引用： KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[i]，顶点Yi的顶标为B [i]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[i]+B[j]>=w[i,j]始终 成立。KM算法的正确性基于以下定理： 若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。 初始时为了使A[i]+B[j]>=w[i,j]恒成立，令A[i]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现： 两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。 两端都不在交错树中的边(i,j)，A[i]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。 X端不在交错树中，Y端在交错树中的边(i,j)，它的A[i]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。 X端在交错树中，Y端不在交错树中的边(i,j)，它的A[i]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。 现在的问题就是求d值了。为了使A[i]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于min{A[i]+B[j]-w[i,j]|Xi在交错树中，Yi不在交错树中}。 以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶 标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数 slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A [i]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的slack值都减去d。
//KM算法求二分图加权完备匹配
//x[i]+y[j]>=w[i][j]不能变，这是KM算法的理论基础
//题目要求最小权，将边的权重取反，并将最后的结果取反即可
#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;
const int M=101,MIN=-205;
struct S
{
int x;
int y;
}man[M],house[M];
int mannum,housenum,num;
int w[M][M]; //存储每条边的权
int link[M]; //与y[j]相连的x[i]
int wman[M],whouse[M]; //可行顶标，也就是顶点的权，man为主体，位于左边
bool vman[M],vhouse[M];//标记交错访问路线
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a>b?b:a;
}
bool find(int i)
{
vman[i]=true;
for(int j=1;j<=num;j++)
{
if(!vhouse[j] && wman[i]+whouse[j] == w[i][j]) //只有当j未被访问且该边满足相等条件时才能交错标记
{
vhouse[j]=true;
if(!link[j] || find(link[j]))
{
link[j]=i;
return true;
}
}
}
return false;
}
void init() //对可行顶标进行初始化，x[i]=max{w[i][j] | 1=<j<=num},y[j]=0
{
int i,j;
for(i=1;i<=num;i++)
{
wman[i]=MIN;
whouse[i]=0;
for(j=1;j<=num;j++)
wman[i]=max(wman[i],w[i][j]);
}
}
int match()
{
int i,j,di,k,temp=0; //di用来进行松弛，扩大完备匹配的范围
init();
memset(link,0,sizeof(link));
for(i=1;i<=num;i++)
{
while(1)
{
di=205;
memset(vman,0,sizeof(vman));
memset(vhouse,0,sizeof(vhouse));
if(find(i)) //如果该边是相等条件就处理下一个顶点
break;
for(k=1;k<=num;k++)//否则找出松弛量di,di=min{x[i]+y[j]-w[i][j]},其中i被标记,j没标记,(i,j)这条边导致了find的失败
{
if(vman[k])
{
for(j=1;j<=num;j++)
if(!vhouse[j])
di=min(di,wman[k]+whouse[j]-w[k][j]);
}
}
for(j=1;j<=num;j++)//削减左边标记点的权重，增加右边标记点的权重，使得(左边标记，右边未标记)边可以满足相等条件
{ //可能会有这样的疑问，既然是(i,j)(i被标记,j没标记)边导致了find的失败，那么我们直接x[i]-=di,使得
if(vman[j]) //(i,j)边满足相等匹配，这样可以吗？是不可以的，因为虽然这条边满足了，但是与i,j顶点相连的原本满足
wman[j]-=di;//相等条件的边不满足了，也就说必须有y[k]+=di操作，其中k是右边标记的顶点。
if(vhouse[j]) //不能省去！！
whouse[j]+=di;//不能省去！！
}
}
}
for(i=0;i<=num;i++) //本来是该temp+=w[link[i][i],不过结果还得取反，所以直接用减去
temp-=w[link[i]][i];
return temp;
}
int main()
{
int n,m,i,j;
char a;
while(cin>>n>>m,m+n)
{
mannum=housenum=0;
for(i=1;i<=n;i++) //提炼出边的权重
for(j=1;j<=m;j++)
{
cin>>a;
if(a=='m')
{
man[++mannum].x=i;
man[mannum].y=j;
}
if(a=='H')
{
house[++housenum].x=i;
house[housenum].y=j;
}
}
num=mannum; //mannum=housenum=num
for(i=1;i<=num;i++)
for(j=1;j<=num;j++)
{
w[i][j]=-(abs(man[i].x - house[j].x)+abs(man[i].y - house[j].y));
}
cout<<match()<<endl;
}
return 0;
}
posted on 2011-09-14 14:59
大大木马 阅读(711)
评论(0) 编辑 收藏 引用