本文主要是介绍poj 2195 Going Home，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
还是KM算法，求最小值的匹配，建图的时候，边都取反就可以转化成求最大值的匹配了。
#include<string.h>
#include<iostream>
# define inf 1000000
using namespace std;
int m,n,x,y,ans;
int map[101][101],visx[101],visy[101],ly[101],lx[101],link[101];
char s[100][100];
int min(int a,int b)
{
if(a<b)
return a;
return b;
}
int max(int a,int b)
{
if(a>b)
return a;
return b;
}
bool dfs(int i)
{
visx[i]=1;
for(int j=0;j<m;j++)
{
if(visy[j]==0&&lx[i]+ly[j]-map[i][j]==0)
{
visy[j]=1;
if(link[j]==-1||dfs(link[j]))
{
link[j]=i;
return true;
}
}
}
return false;
}
void km()
{
for(int i=0;i<m;i++)
{
lx[i]=-inf;
for(int j=0;j<m;j++)
lx[i]=max(lx[i],map[i][j]);
}
memset(ly,0,sizeof(ly));
memset(link,-1,sizeof(link));
for(int i=0;i<m;i++)
{
while(1)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(dfs(i)) break;
int d=inf;
for(int j=0;j<m;j++)
{
if(visx[j]==1)
for(int k=0;k<m;k++)
if(visy[k]==0)
d=min(d,lx[j]+ly[k]-map[j][k]);
}
for(int j=0;j<m;j++)
{
if(visx[j]==1) lx[j]-=d;
if(visy[j]==1) ly[j]+=d;
}
}
}
}
int main()
{
while(cin>>x>>y)
{
if(x==0&&y==0) break;
memset(map,0,sizeof(map));
for(int i=1;i<=x;i++)
for(int j=1;j<=y;j++)
{
cin>>s[i][j];
}
n=0;m=0;
ans=0;
for(int i=1;i<=x;i++)
{
for(int j=1;j<=y;j++)
{
if(s[i][j]=='m')
{
n=0;
for(int k=1;k<=x;k++)
for(int v=1;v<=y;v++)
{
if(s[k][v]=='H')
{
map[m][n]=-(abs(i-k)+abs(j-v));
n++;
}
}
m++;
}
}
}
km();
for(int i=0;i<m;i++)
{
ans+=map[link[i]][i];
}
cout<<0-ans<<endl;
}
return 0;
}
这篇关于poj 2195 Going Home的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
