题解：
简单KM
把每一个男的和房子分离
代码:
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int NN=1005,MM=10005; int a[NN][NN],v[NN][NN],g[NN][NN],lk[MM],lx[MM],ly[MM]; int visx[MM],visy[MM],slack[MM],N,M,n,n1,n2,cnt,ans; int dfs(int x) { visx[x]=cnt; for (int y=1;y<=n;y++) { if (visy[y]==cnt) continue; int t=lx[x]+ly[y]-g[x][y]; if (!t) { visy[y]=cnt; if (!lk[y]||dfs(lk[y])){lk[y]=x;return 1;} } else if (slack[y]>t) slack[y]=t; } return 0; } void KM() { memset(lk,0,sizeof(lk)); memset(lx,0,sizeof(lx)); memset(ly,0,sizeof(ly)); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++)lx[i]=max(lx[i],g[i][j]); for (int x=1;x<=n;++x) { for (int i=1;i<=n;i++)slack[i]=1e9; while (cnt++,!dfs(x)) { int d=1e9; for (int i=1;i<=n;i++) if (visy[i]!=cnt) d=min(d,slack[i]); for (int i=1;i<=n;i++) { if (visx[i]==cnt) lx[i]-=d; if (visy[i]==cnt) ly[i]+=d; else slack[i]-=d; } } } return; } void work() { n1=n2=ans=0; for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) { for (a[i][j]=getchar();a[i][j]!='.'&&a[i][j]!='m'&&a[i][j]!='H';a[i][j]=getchar()); if (a[i][j]=='m') v[i][j]=++n1; if (a[i][j]=='H') v[i][j]=++n2; } for (int i=1;i<=N;i++) for (int j=1;j<=M;++j) { if (a[i][j]!='m') continue; for (int p=1;p<=N;p++) for (int q=1;q<=M;q++) if (a[p][q]=='H') g[v[i][j]][v[p][q]]=-abs(i-p)-abs(j-q); } n=n1; KM(); for (int i=1;i<=n;i++)ans+=lx[i]+ly[i]; printf("%d ",-ans); return; } int main() { while (~scanf("%d%d",&N,&M)&&N|M) work(); return 0; }