原文链接：http://www.cnblogs.com/ACAC/archive/2010/05/17/1737729.html

/*pku 2195 KM算法求最小权二分匹配*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAX 101
int hx[MAX],mx[MAX],hy[MAX],my[MAX];
char map[MAX][MAX];
int usedx[MAX],usedy[MAX],match[MAX],w[MAX][MAX],n,m;//// match[]存放的右顶点的匹配信息,w[][]存放的是权值,N是右顶点数
int lx[MAX],ly[MAX],slack[MAX];// lx[],ly[]分别存放的是左右顶标的信息,slack[]是松弛量
int k1,k2;
int dfs(int x)
{
usedx[x]=1;
for(int y=0;y<k2;y++)
{
if(!usedy[y])
{
int temp=lx[x]+ly[y]-w[x][y];
if(temp==0)
{
usedy[y]=1;
if(match[y]==-1 || dfs(match[y]))
{
match[y]=x;
return 1;
}
}
else
{
if(slack[y]>temp)
{
slack[y]=temp;
}
}
}
}
return 0;
}
void KM()
{
int i,j;
memset(match,-1,sizeof(match)); //match[]中存储的是y的匹配信息
for(i=0;i<k1;i++)
{
lx[i]=-999999999; //每个X节点的可行顶标设为它出发的所有弧的最大权
for(j=0;j<k2;j++)
{
if(lx[i]<w[i][j])
{
lx[i]=w[i][j];
}
}
}
memset(ly,0,sizeof(ly));
for(int x=0;x<k1;x++)
{
for(j=0;j<k2;j++)
{
slack[j]=999999999;
}
while(1)
{
memset(usedx,0,sizeof(usedx));
memset(usedy,0,sizeof(usedy));
if(dfs(x)) // 用匈牙利算法寻找完备匹配
{
break;
}
int min=99999999;
for(i=0;i<k2;i++)
{
if(!usedy[i] && min>slack[i])
{
min=slack[i];
}
}
for(i=0;i<k1;i++)
{
if(usedx[i])
{
lx[i]-=min;
}
}
for(i=0;i<k2;i++)
{
if(usedy[i])
{
ly[i]+=min;
}
else
{
slack[i]-=min;
}
}
}
}
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF && n || m)
{
for(i=0;i<n;i++)
scanf("%s",map[i]);
k1=k2=0;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(map[i][j]=='m')
{
hx[k1]=i;
hy[k1++]=j;
}
else if(map[i][j]=='H')
{
mx[k2]=i;
my[k2++]=j;
}
}
}
for(i=0;i<k1;i++)
{
for(j=0;j<k2;j++)
{
w[i][j]=-(fabs(hx[i]-mx[j])+fabs(hy[i]-my[j]));
}
}
KM();
int ans=0;
for(i=0;i<k2;i++)
{
ans+=-w[match[i]][i];
}
printf("%d\n",ans);
}
return 0;
}

 

转载于:https://www.cnblogs.com/ACAC/archive/2010/05/17/1737729.html