【题意】：给出一个row*col的矩阵，m表示人，H表示房子，.表示空地，人数和房子数相等。 现在要让所有的人都进入不同的房子内，求最少步数？
【题解】：很裸的最小费用流，不解释了。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "queue"
4 #include "cstring"
5 #include "cmath"
6 using namespace std;
7 const int inf = 1 << 30;
8 #define maxn 5005
9 #define maxm 500005
10 #define MAX 105
11 int n, r, c, s, t;
12 int eh[maxn], dist[maxn], low[maxn], tot, pre[maxn], ans, anscost, m, h;
13 bool visit[maxn];
14 char maz[MAX][MAX];
15
16 struct Edge {
17 int u, v, cost, cap, flow, next;
18 }et[maxm];
19
20 struct node {
21 int x, y;
22 }man[maxn], house[maxn];
23
24 void init() {
25 tot = 0;
26 m = h = 0;
27 memset(eh, -1, sizeof(eh));
28 }
29
30 void add(int u, int v, int cost, int cap, int flow) {
31 Edge e = {u, v, cost, cap, flow, eh[u]};
32 et[tot] = e;
33 eh[u] = tot++;
34 }
35
36 void addedge(int u, int v, int cost, int cap) {
37 add(u, v, cost, cap, 0), add(v, u, -cost, 0, 0);
38 }
39
40 int getdist(int i, int j) {
41 return abs(man[i].x - house[j].x) + abs(man[i].y - house[j].y);
42 }
43
44 bool spfa() {
45 queue<int> que;
46 fill(&dist[0], &dist[maxn], inf);
47 memset(visit, false, sizeof(visit));
48 memset(pre, -1, sizeof(pre));
49 low[s] = inf, visit[s] = true, dist[s] = 0;
50 que.push(s);
51 while(!que.empty()) {
52 int u = que.front();
53 que.pop();
54 visit[u] = false;
55 for(int i = eh[u]; i != -1; i = et[i].next) {
56 int v = et[i].v, cost = et[i].cost, cap = et[i].cap, flow = et[i].flow;
57 if(cap - flow && dist[v] > dist[u] + cost) {
58 dist[v] = dist[u] + cost;
59 pre[v] = i;
60 low[v] = min(low[u], cap - flow);
61 if(!visit[v]) {
62 que.push(v);
63 visit[v] = true;
64 }
65 }
66 }
67 }
68 return dist[t] != inf;
69 }
70
71 void costflow() {
72 ans = anscost = 0;
73 while(spfa()) {
74 int x = pre[t];
75 ans += low[t];
76 anscost += low[t] * dist[t];
77 while(x != -1) {
78 et[x].flow += low[t];
79 et[x^1].flow -= low[t];
80 x = pre[et[x].u];
81 }
82 }
83 }
84
85 int main() {
86 while(~scanf("%d%d", &r, &c)) {
87 getchar();
88 if(!r && !c) break;
89 init();
90 for(int i = 0; i < r; i++) {
91 for(int j = 0; j <= c; j++) {
92 scanf("%c", &maz[i][j]);
93 if(maz[i][j] == 'm') {
94 m++;
95 man[m].x = i, man[m].y = j;
96 }
97 if(maz[i][j] == 'H') {
98 h++;
99 house[h].x = i, house[h].y = j;
100 }
101 }
102 }
103 s = 0, t = m + h + 1 ,n = m + h + 2;
104 for(int i = 1; i <= m; i++) addedge(s, i, 0, 1);
105 for(int i = 1; i <= h; i++) addedge(i + m, t, 0, 1);
106 for(int i = 1; i <= m; i++)
107 for(int j = 1; j <= h; j++)
108 addedge(i, m + j, getdist(i, j), 1);
109 costflow();
110 printf("%d\n", anscost);
111 }
112 }
113