题目：http://poj.org/problem?id=2195
处理出每个人到每个门的曼哈顿距离，分别建立容量为1费用为曼哈顿距离的边，在源点和每个人人之间建立容量为1费用为0的边，在门和汇点之间建立容量为1费用为0的边，然后跑最小费用流即可。
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef pair<int,int> P;
const int maxv = ;
const int inf = 0x3f3f3f3f;
struct edge{
int to,cap,cost,rev;
};
int V;
vector<edge> g[maxv];
int h[maxv];
int dist[maxv];
int prevv[maxv],preve[maxv];
void addedge(int from,int to,int cap,int cost){
edge t;
t.to = to;t.cap = cap;t.cost = cost;t.rev = g[to].size();
g[from].push_back(t);
t.to = from;t.cap = ;t.cost = -cost;t.rev = g[from].size()-;
g[to].push_back(t);
}
int solve(int s,int t,int f){
int res = ;
memset(h,,sizeof(h));
while(f > ){
priority_queue<P,vector<P>,greater<P> > que;
memset(dist,inf,sizeof(dist));
dist[s] = ;
que.push(P(,s));
while(!que.empty()){
P p = que.top();
que.pop();
int v = p.second;
if(dist[v] < p.first)
continue;
for(int i = ;i<g[v].size();i++){
edge &e = g[v][i];
if(e.cap> && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
dist[e.to] = dist[v]+e.cost+h[v]-h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
que.push(P(dist[e.to],e.to));
}
}
}
if(dist[t] == inf){
return -;
}
for(int i = ;i<=t;i++)
h[i] += dist[i];
int d = f;
for(int i = t;i!=s;i = prevv[i]){
d = min(d,g[prevv[i]][preve[i]].cap);
}
f -= d;
res += d*h[t];
for(int i = t;i!=s;i = prevv[i]){
edge &e = g[prevv[i]][preve[i]];
e.cap -= d;
g[i][e.rev].cap += d;
}
}
return res;
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m) && n && m){
vector<P> mm,hh;
char ch;
for(int i = ;i<=n;i++){
for(int j = ;j<=m;j++){
scanf(" %c",&ch);
if(ch == 'm')
mm.push_back(P(i,j));
if(ch == 'H')
hh.push_back(P(i,j));
}
}
for(int i = ;i<=*mm.size()+;i++)
g[i].clear();
for(int i = ;i<mm.size();i++){
for(int j = ;j<hh.size();j++){
addedge(i+,mm.size()+j+,,abs(mm[i].first-hh[j].first)+abs(mm[i].second-hh[j].second));
}
}
int s = ,t = *mm.size()+;
for(int i = ;i<mm.size();i++)
addedge(s,i+,,);
for(int i = ;i<hh.size();i++)
addedge(mm.size()+i+,t,,);
cout << solve(s,t,mm.size()) << endl;
}
}