hdu 1533 Going Home（二分圖）

 


#include<stdio.h>

#include<string.h>
#include<math.h>


#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define inf 100000000


struct node
{
int x,y;
}house[1010],men[1010];


int n;
int map[1010][1010],sx[1010],sy[1010],lx[1010],ly[1010],match[1010];


int find(int k)
{
int i;
sx[k]=1;
for(i=1;i<=n;i++)
{
if(map[k][i]==lx[k]+ly[i]&&sy[i]==0)
{
sy[i]=1;
if(match[i]==0||find(match[i])==1)
{
match[i]=k;
return 1;
}
}
}
return 0;
}


int KM()
{
int i,j,k,ans=0;
memset(match,0,sizeof(match));
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
lx[i]=max(lx[i],map[i][j]);
for(i=1;i<=n;i++)
{
while(1)
{
memset(sx,0,sizeof(sx));
memset(sy,0,sizeof(sy));
if(find(i))break;
else
{
int a=inf;
for(j=1;j<=n;j++)
if(sx[j])
{
for(k=1;k<=n;k++)
if(!sy[k])
a=min(a,lx[j]+ly[k]-map[j][k]);
}
for(j=1;j<=n;j++)
{
if(sx[j])lx[j]-=a;
if(sy[j])ly[j]+=a;
}
}
}
}
for(i=1;i<=n;i++)
ans+=map[match[i]][i];
return ans;
}


int main()
{
int w,e,i,j,flag1,flag2;
char aa[1010][1010];
while(scanf("%d%d",&w,&e),w+e)
{
flag1=0;flag2=0;
for(i=0;i<w;i++)
{
scanf("%s",aa[i]);
for(j=0;j<e;j++)
{
if(aa[i][j]=='H')
{
flag2++;
house[flag2].x=i;
house[flag2].y=j;
}
else if(aa[i][j]=='m')
{
flag1++;
men[flag1].x=i;
men[flag1].y=j;
}
}
}
for(i=1;i<=flag1;i++)
for(j=1;j<=flag2;j++)
map[i][j]=-(abs(house[j].x-men[i].x)+abs(house[j].y-men[i].y));
n=flag1;
int ans=KM();
printf("%d\n",-ans);
}
return 0;
}