pku 2195 KM算法求最小权二分匹配

/*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;
}