还是主要寻找个增广路，用spfa寻找增广路。
邻接表存。
这是个模板题：
构图的话，设置一个超级源点，超级汇点，再人一个集合，房子一个集合，在任何每个房子间连一条流量为1，费用为距离的边，超级源点和人连 流量为1，费用为0,，房子和超级汇点间也同样连边。
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=1000,maxm=100000,inf=1<<26;
struct Edge
{
Edge(){};
Edge(int a,int b,int c,int d) {v=a; f=b; w=c; nxt=d;}
int v,f,w,nxt;
};
struct point
{
int x,y;
} hh[300],mm[300];
int g[maxn+10];
struct Edge e[maxm+10];
int nume;
int src,sink;
char Map[300][300];
queue<int>que;
bool inQue[maxn+10];
int dist[maxn+10];
int pree[maxn+10],prev[maxn+10];
void add(int u,int v,int f,int w)
{
e[++nume] = Edge(v,f,w,g[u]);
g[u]=nume;
e[++nume] = Edge(u,0,-w,g[v]);
g[v]=nume;
}
bool findPath()
{
while(!que.empty()) que.pop();
que.push(src);
int i;
//memeset(dist,63,sizeof(dist));
for(i=0;i<=sink+10;i++) dist[i]=inf;
dist[src]=0;
inQue[src]=true;
while(!que.empty()){
int u=que.front();
que.pop();
for(i = g[u]; i ; i=e[i].nxt){
if(e[i].f>0&&dist[u]+e[i].w<dist[e[i].v]){
dist[e[i].v]=dist[u]+e[i].w;
prev[e[i].v]=u;
pree[e[i].v]=i;
if(!inQue[e[i].v]){
inQue[e[i].v]=true;
que.push(e[i].v);
}
}
}
inQue[u]=false;
}
if(dist[sink] < inf ) return true;
return false;
}
int augment()
{
int u=sink;
int delta=inf;
while(u!=src){
if(e[pree[u]].f<delta) delta=e[pree[u]].f;
u=prev[u];
}
u=sink;
while(u!=src){
e[pree[u]].f-=delta;
e[pree[u]^1].f+=delta;
u=prev[u];
}
return dist[sink]*delta;
}
int mincostflow()
{
int cur=0;
while(findPath()){
cur+=augment();
}
return cur;
}
int main()
{
int n,m,i,j;
while(scanf("%d%d",&n,&m),m||n){
getchar();
memset(g,0,sizeof(g));
nume=1;
int mh1=0,mh2=0;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
scanf("%c",&Map[i][j]);
if(Map[i][j]==‘H‘) {
hh[mh1].x=i;
hh[mh1++].y=j;
}
if(Map[i][j]==‘m‘){
mm[mh2].x=i;
mm[mh2++].y=j;
}
}
getchar();
}
int mh=mh1;
src=0;sink=2*mh+1;
for(i=1;i<=mh;i++) add(0,i,1,0);
for(i=mh+1;i<=2*mh;i++) add(i,2*mh+1,1,0);
for(i=0;i<mh;i++)
for(j=0;j<mh;j++){
int tempx=hh[i].x-mm[j].x;
int tempy=hh[i].y-mm[j].y;
add(i+1,mh+j+1,1,abs(tempx)+abs(tempy));
}
printf("%d\n",mincostflow());
}
}