题意：
给一个n*m的矩阵，其中由k个人和k个房子，给每个人匹配一个不同的房子，要求所有人走过的曼哈顿距离之和最短。
输入：
多组输入数据。
每组输入数据第一行是两个整型n, m，表示矩阵的长和宽。
接下来输入矩阵。
输出：
输出最短距离。
题解：
标准的最小费用最大流算法，或者用KM算法。由于这里是要学习费用流，所以使用前者。
最小费用最大流，顾名思义，就是在一个网络中，不止存在流量，每单位流量还存在一个费用。由于一个网络的最大流可能不止一种，所以，求出当前网络在流量最大的情况下的最小花费。
直接百度百科最小费用最大流算法，可以看到两种思路——
- 先求出最大流。然后寻找是否存在路径，可以使这个网络在最大流不变的情况下减小费用。如果存在，则改变网络。不停迭代，知道不存在更优的路径为止——但是我还没有找到这种方法的实现方式。我自己也没有试着实现。
- 在网络之外构造一个新图，这张图记录已经存在的路径的长度（即此路径单位流量的费用），需要注意的是路径是有向路径（反向路径的长度是正向路径的相反数，原因和最大流中每选择一条边，都要给网络构造）。然后寻找增广路径（也就是从源点到汇点的一条路），这条路同时满足在构造的图是最短路。然后按照求最大流的方法修改原网络，反复迭代，保证每次找到的增广路都是当前残余网络在构造的图中的最短路。那么最终得到的最大流一定是最小费用最大流（贪心大法）。
以上是算最小费用最大流的方法。
具体的算法，可以使用EK+spfa算法来实现。
针对这道题，我们需要先构造网络。
我们设0节点为源点，接下来1——k节点为人，k+1——2*k为房子，2*k+1为汇点。
源点到每个人连一条边，每个人到每个房子连一条边，每个房子到汇点连一条边（不要忘了是有向边），每条边的权为1。
接下来构造费用图。源点到每个人一条边，权值为0，每个人到每个房子一条边，权值为它们之间的曼哈顿距离。每个放在到汇点一条边，权值为0。
然后带到算法里计算。
实现见代码——
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 8 const int N = 110; 9 const int M = 100000010; 10 11 struct Node 12 { 13 int x, y; 14 }man[N], house[N]; //人，房子的横纵坐标 15 16 char mp[N][N]; 17 int cost[2*N][2*N], flow[2*N][2*N]; //距离图和流网络 18 int pre[2*N], low[2*N], dis[2*N]; //分别记录当前节点的父节点，当前路径的最小流量，spfa中的最短距离 19 bool vis[2*N]; //标记当前节点是否在队列中 20 int n, m; 21 int ans; 22 int mn, hs, k, kk; //分别表示人的数量+1，房子的数量+1，人的数量，邻接矩阵每一维的大小 23 24 void init() 25 { 26 mn = 1, hs = 1; 27 for(int i = 0; i < n; i++) 28 { 29 scanf("%s", mp[i]); 30 for(int j = 0; j < m; j++) 31 { 32 if(mp[i][j] == 'm') {man[mn].x = i; man[mn++].y = j;} 33 if(mp[i][j] == 'H') {house[hs].x = i; house[hs++].y = j;} 34 } 35 } 36 k = hs-1; 37 kk = 2*k+1; 38 for(int i = 0; i < kk; i++) 39 { 40 for(int j = 0; j < kk; j++) cost[i][j] = M; 41 } 42 memset(flow, 0, sizeof(flow)); 43 for(int i = 1; i <= k; i++) 44 { 45 for(int j = k+1; j < kk; j++) 46 { 47 cost[i][j] = abs(man[i].x-house[j-k].x)+abs(man[i].y-house[j-k].y); //人到房子的距离为曼哈顿距离 48 cost[j][i] = -cost[i][j]; //反向距离 49 flow[i][j] = 1; //人到房子的流网络 50 } 51 cost[i][0] = cost[0][i] = 0; //源点到人，人到源点的距离 52 flow[0][i] = 1; //源点到人的流网络 53 cost[i+k][kk] = cost[kk][i+k] = 0; //汇点到房子，房子到汇点的距离 54 flow[i+k][kk] = 1; //房子到汇点的流网络 55 } 56 ans = 0; 57 } 58 59 int Min(int x, int y) 60 { 61 return x < y ? x : y; 62 } 63 64 bool spfa() 65 { 66 for(int i = 0; i <= kk; i++) 67 { 68 dis[i] = M; 69 pre[i] = -1; 70 vis[i] = 0; 71 low[i] = M; 72 } 73 queue<int> que; 74 que.push(0); 75 vis[0] = 1; 76 dis[0] = 0; 77 while(!que.empty()) 78 { 79 int p = que.front(); 80 que.pop(); 81 vis[p] = 0; 82 for(int i = 0; i <= kk; i++) 83 { 84 if(flow[p][i] && dis[i] > dis[p]+cost[p][i]) 85 { 86 dis[i] = dis[p]+cost[p][i]; 87 pre[i] = p; 88 low[i] = Min(low[p], flow[p][i]); 89 if(!vis[i]) 90 { 91 vis[i] = 1; 92 que.push(i); 93 } 94 } 95 } 96 } 97 return dis[kk] != M; 98 } 99 100 void work() 101 { 102 while(spfa()) //如果存在路径，则计算流量 103 { 104 int x = kk; 105 while(pre[x] != -1) 106 { 107 flow[pre[x]][x] -= low[kk]; 108 flow[x][pre[x]] += low[kk]; 109 x = pre[x]; 110 } 111 ans += dis[kk]; //计算距离和 112 } 113 } 114 115 void outit() 116 { 117 printf("%d ", ans); 118 } 119 120 int main() 121 { 122 while(~scanf("%d%d", &n, &m) && (n+m)) 123 { 124 init(); 125 work(); 126 outit(); 127 } 128 return 0; 129 }