题目大意：
有一个最大是100 * 100 的网格图，上面有 s 个 房子和人，人每移动一个格子花费1的代价，求最小代价让所有的人都进入一个房子。每个房子只能进入一个人。
算法讨论：
注意是KM 和 MCMF算法，我写的是MCMF算法，一开始想的是连10000个点，但是不会连那些大众点之间的边，只会连超级点和普通点之间的边。后来觉得只要连房子点和
人点就可以了。连从人到房子的边，容量是1，花费是他们之间的曼哈顿距离，然后超级源点和超级汇点像上面那样连接，注意连点的时候把他们每个点都具体化一下，就是把点值
都精确到一个连续的范围内去。然后做从超级源点到超级汇点的MCMF算法就可以了。至于那10000个之间的连边，觉得虽然效率不高，但是还是有必要考虑一下。大家有知道的撒
告诉一下。感谢万分。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue> using namespace std; struct MCMF{
static const int N = * + ;
static const int M = * * + ;
static const int oo = 0x3f3f3f3f; int n, m, s, t, tot;
int first[N], next[M];
int u[M], v[M], cap[M], flow[M], cost[M];
int dis[N], a[N], inque[N], pre[N]; void Clear(){memset(first, -, sizeof first);tot = ;} void Add(int from, int to, int cp, int flw, int ct){
u[tot] = from; v[tot] = to; cap[tot] = cp; flow[tot] = ; cost[tot] = ct;
next[tot] = first[u[tot]];
first[u[tot]] = tot; ++ tot;
u[tot] = to; v[tot] = from; cap[tot] = ; flow[tot] = ; cost[tot] = -ct;
next[tot] = first[u[tot]];
first[u[tot]] = tot; ++ tot;
} bool bfs(int &flw, int &ct){
for(int i = ; i <= n + ; ++ i) dis[i] = oo;
memset(inque, , sizeof inque);
dis[s] = ; pre[s] = ; a[s] = oo; inque[s] = ; queue <int> q;
q.push(s);
while(!q.empty()){
int now = q.front(); q.pop();
inque[now] = ; for(int i = first[now]; i != -; i = next[i]){
if(cap[i] > flow[i] && dis[v[i]] > dis[now] + cost[i]){
dis[v[i]] = dis[now] + cost[i];
a[v[i]] = min(a[now], cap[i] - flow[i]);
pre[v[i]] = i;
if(!inque[v[i]]){
inque[v[i]] = ; q.push(v[i]);
}
}
}
} if(dis[t] == oo) return false;
flw += a[t];
ct += dis[t] * a[t]; int now = t;
while(now != s){
flow[pre[now]] += a[t];
flow[pre[now]^] -= a[t];
now = u[pre[now]];
}
return true;
} int MinCostMaxFlow(int s, int t){
this->s = s;this->t = t;
int flw = , ct = ;
while(bfs(flw, ct));
return ct;
}
}Net; struct Position{
int l, r, id;
Position(int _l=, int _r=, int _id=): l(_l), r(_r), id(_id){}
}mm[], HH[]; int ns, ms, cnt1, cnt2, tp1, tp2;
char str[][]; void Solve(){
for(int i = ; i <= tp1; ++ i){
for(int j = ; j <= tp2; ++ j){
int x1 = mm[i].l, y1 = mm[i].r;
int x2 = HH[j].l, y2 = HH[j].r;
Net.Add(mm[i].id, HH[j].id, , , abs(x1-x2) + abs(y1-y2));
}
}
} int main(){ while(scanf("%d%d", &ns, &ms) && ns && ms){
Net.Clear();
cnt1 = cnt2 = ;
tp1 = tp2 = ;
for(int i = ; i <= ns; ++ i)
scanf("%s", str[i] + );
for(int i = ; i <= ns; ++ i){
for(int j = ; j <= ms; ++ j){
if(str[i][j] == 'm') ++ tp1;
else if (str[i][j] == 'H') ++ tp2;
}
}
Net.n = tp1 + tp2;
for(int i = ; i <= ns; ++ i){
for(int j = ; j <= ms; ++ j){
if(str[i][j] == 'm'){
++ cnt1;
Net.Add(, cnt1, , , );
mm[cnt1] = (Position){i, j, cnt1};
}
}
}
for(int i = ; i <= ns; ++ i){
for(int j = ; j <= ms; ++ j){
if(str[i][j] == 'H'){
++ cnt2;
Net.Add(tp1 + cnt2, Net.n + , , , );
HH[cnt2] = (Position){i, j, tp1 + cnt2};
}
}
}
Solve();
printf("%d\n", Net.MinCostMaxFlow(, Net.n + ));
} return ;
}
POJ 2195/HDU 1533