就是最基本的二分图最优匹配，将每个人向每个房子建一条边，权值就是他们manhattan距离。然后对所有权值取反，求一次最大二分图最优匹配，在将结果取反就行了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Maxn 110
using namespace std;
int n;//点的数目
int lx[Maxn],ly[Maxn]; //顶点标号
int weight[Maxn][Maxn];// 边的权值
int slack[Maxn];// Y(i)的松弛函数
int sx[Maxn],sy[Maxn]; //标记X,Y中的顶点是否在交错路径上
int match[Maxn];//Y的匹配
struct Point{
int x,y;
}house[Maxn],man[Maxn];
int Dis(Point a,Point b)
{
return abs(a.x-b.x)+abs(a.y-b.y);
}
int dfs(int u)
{
sx[u]=;
int i;
for(i=;i<=n;i++)
{
if(!sy[i]&&lx[u]+ly[i]==weight[u][i])//如果在相等子图中，且未被访问
{
sy[i]=;
if(match[i]==-||dfs(match[i]))
{
match[i]=u;
return ;
}
}
else
if(!sy[i])//Y(i)不在交错路径当中
slack[i]=min(slack[i],lx[u]+ly[i]-weight[u][i]);
}
return ;
}
int bestmatch(bool f)
{
int i,j;
if(!f)
{
for(i=;i<=n;i++)
{
lx[i]=-0x7FFFFFFF;
ly[i]=;
for(j=;j<=n;j++)
{
weight[i][j]=-weight[i][j];
lx[i]=max(lx[i],weight[i][j]);
}
}
}
else
{
for(i=;i<=n;i++)
{
lx[i]=;
ly[i]=;
for(j=;j<=n;j++)
lx[i]=max(lx[i],weight[i][j]);
}
}
memset(match,-,sizeof(match));
for(i=;i<=n;i++)
while()
{
memset(sx,,sizeof(sx));
memset(sy,,sizeof(sy));
for(j=;j<=Maxn-;j++)
slack[j]=0x7FFFFFFF;
if(dfs(i))
break;
int dx=0x7FFFFFFF;
for(j=;j<=n;j++)
dx=min(dx,slack[j]);
for(j=;j<=n;j++)
{
if(sx[j])
lx[j]-=dx;
if(sy[j])
ly[j]+=dx;
}
}
int ans=;
for(i=;i<=n;i++)
ans+=weight[match[i]][i];
if(!f)
ans=-ans;
return ans;
}
int main()
{
int i,j,N,M,a,b;
char str[];
while(scanf("%d%d",&N,&M),N||M)
{
a=b=;
for(i=;i<=N;i++)
{
scanf("%s",&str);
for(j=;j<M;j++)
{
if(str[j]=='H')
house[++a].x=i,house[a].y=j;
if(str[j]=='m')
man[++b].x=i,man[b].y=j;
}
}
n=a;
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
weight[i][j]=Dis(man[i],house[j]);
}
printf("%d\n",bestmatch(false));
}
return ;
}
最小费油最大流解法：
#include<iostream>
#include<cstring>
#include<cstring>
using namespace std;
const int size = ;
const int INF = 0x7fffffff;
struct Point{
int x,y;
};
struct Edge
{
int to;
int vol;
int cost;
int next;
}e[size*];
Point house[],man[];
int index[size];
int edgeNum;
int pre[size], pos[size];
int dis[size], que[size*];
bool vis[size];
void insert(int from, int to, int vol, int cost)
{
e[edgeNum].to = to;
e[edgeNum].vol = vol;
e[edgeNum].cost = cost;
e[edgeNum].next = index[from];
index[from] = edgeNum++;
e[edgeNum].to = from;
e[edgeNum].vol = ;
e[edgeNum].cost = -cost;
e[edgeNum].next = index[to];
index[to] = edgeNum++;
}
int DIS(Point p1,Point p2)
{
return abs(p1.x-p2.x)+abs(p1.y-p2.y);
}
bool spfa(int s, int t)
{
int i;
memset(pre, -, sizeof(pre));
memset(vis, , sizeof(vis));
int head, tail; head = tail = ;
for(i = ; i < size; i++)
dis[i] = INF;
que[tail++] = s;
pre[s] = s;
dis[s] = ;
vis[s] = ;
while(head != tail)
{ int now = que[head++];
vis[now] = ;
for(i = index[now]; i != -; i = e[i].next)
{
int adj = e[i].to;
if(e[i].vol > && dis[now] + e[i].cost < dis[adj])
{
dis[adj] = dis[now] + e[i].cost;
pre[adj] = now;
pos[adj] = i;
if(!vis[adj])
{
vis[adj] = ;
que[tail++] = adj;
}
}
}
}
return pre[t] != -;
}
int MinCostFlow(int s, int t, int flow)
{
int i;
int cost = ;
flow = ;
while(spfa(s, t))
{
int f = INF;
for(i = t; i != s; i = pre[i])
if (e[pos[i]].vol < f) f = e[pos[i]].vol;
flow += f; cost += dis[t] * f;
for(i = t; i != s; i = pre[i])
{
e[pos[i]].vol -= f;
e[pos[i] ^ ].vol += f;
}
}
return cost; // flow是最大流值
}
int main()
{
int n,m,i,j,u,v;
char c;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==&&m==)
break;
memset(index,-,sizeof(index));
int k1=,k2=;
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
{
cin>>c;
switch(c)
{
case '.':break;
case 'm':man[++k1].x=i,man[k1].y=j;break;
case 'H':house[++k2].x=i,house[k2].y=j;break;
}
}
}
for(i=;i<=k1;i++)
{ for(j=;j<=k2;j++)
{
insert(i,j+k1,,DIS(man[i],house[j]));
}
insert(,i,,);
insert(i+k1,k1+k2+,,);
}
//spfa(0,k1+k2+1);
int ans=MinCostFlow(,k1+k2+,);
printf("%d\n",ans);
}
return ;
}