题意：
给一个n*m的矩阵，其中由k个人和k个房子，给每个人匹配一个不同的房子，要求所有人走过的曼哈顿距离之和最短。
输入：
多组输入数据。
每组输入数据第一行是两个整型n, m，表示矩阵的长和宽。
接下来输入矩阵。
输出：
输出最短距离。
题解：
标准的最小费用最大流算法，或者用KM算法。由于这里是要学习费用流，所以使用前者。
最小费用最大流，顾名思义，就是在一个网络中，不止存在流量，每单位流量还存在一个费用。由于一个网络的最大流可能不止一种，所以，求出当前网络在流量最大的情况下的最小花费。
直接百度百科最小费用最大流算法，可以看到两种思路——
- 先求出最大流。然后寻找是否存在路径，可以使这个网络在最大流不变的情况下减小费用。如果存在，则改变网络。不停迭代，知道不存在更优的路径为止——但是我还没有找到这种方法的实现方式。我自己也没有试着实现。
- 在网络之外构造一个新图，这张图记录已经存在的路径的长度（即此路径单位流量的费用），需要注意的是路径是有向路径（反向路径的长度是正向路径的相反数，原因和最大流中每选择一条边，都要给网络构造）。然后寻找增广路径（也就是从源点到汇点的一条路），这条路同时满足在构造的图是最短路。然后按照求最大流的方法修改原网络，反复迭代，保证每次找到的增广路都是当前残余网络在构造的图中的最短路。那么最终得到的最大流一定是最小费用最大流（贪心大法）。
以上是算最小费用最大流的方法。
具体的算法，可以使用EK+spfa算法来实现。
针对这道题，我们需要先构造网络。
我们设0节点为源点，接下来1——k节点为人，k+1——2*k为房子，2*k+1为汇点。
源点到每个人连一条边，每个人到每个房子连一条边，每个房子到汇点连一条边（不要忘了是有向边），每条边的权为1。
接下来构造费用图。源点到每个人一条边，权值为0，每个人到每个房子一条边，权值为它们之间的曼哈顿距离。每个放在到汇点一条边，权值为0。
然后带到算法里计算。
实现见代码——
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std; const int N = ;
const int M = ; struct Node
{
int x, y;
}man[N], house[N]; //人，房子的横纵坐标 char mp[N][N];
int cost[*N][*N], flow[*N][*N]; //距离图和流网络
int pre[*N], low[*N], dis[*N]; //分别记录当前节点的父节点，当前路径的最小流量，spfa中的最短距离
bool vis[*N]; //标记当前节点是否在队列中
int n, m;
int ans;
int mn, hs, k, kk; //分别表示人的数量+1，房子的数量+1，人的数量，邻接矩阵每一维的大小 void init()
{
mn = , hs = ;
for(int i = ; i < n; i++)
{
scanf("%s", mp[i]);
for(int j = ; j < m; j++)
{
if(mp[i][j] == 'm') {man[mn].x = i; man[mn++].y = j;}
if(mp[i][j] == 'H') {house[hs].x = i; house[hs++].y = j;}
}
}
k = hs-;
kk = *k+;
for(int i = ; i < kk; i++)
{
for(int j = ; j < kk; j++) cost[i][j] = M;
}
memset(flow, , sizeof(flow));
for(int i = ; i <= k; i++)
{
for(int j = k+; j < kk; j++)
{
cost[i][j] = abs(man[i].x-house[j-k].x)+abs(man[i].y-house[j-k].y); //人到房子的距离为曼哈顿距离
cost[j][i] = -cost[i][j]; //反向距离
flow[i][j] = ; //人到房子的流网络
}
cost[i][] = cost[][i] = ; //源点到人，人到源点的距离
flow[][i] = ; //源点到人的流网络
cost[i+k][kk] = cost[kk][i+k] = ; //汇点到房子，房子到汇点的距离
flow[i+k][kk] = ; //房子到汇点的流网络
}
ans = ;
} int Min(int x, int y)
{
return x < y ? x : y;
} bool spfa()
{
for(int i = ; i <= kk; i++)
{
dis[i] = M;
pre[i] = -;
vis[i] = ;
low[i] = M;
}
queue<int> que;
que.push();
vis[] = ;
dis[] = ;
while(!que.empty())
{
int p = que.front();
que.pop();
vis[p] = ;
for(int i = ; i <= kk; i++)
{
if(flow[p][i] && dis[i] > dis[p]+cost[p][i])
{
dis[i] = dis[p]+cost[p][i];
pre[i] = p;
low[i] = Min(low[p], flow[p][i]);
if(!vis[i])
{
vis[i] = ;
que.push(i);
}
}
}
}
return dis[kk] != M;
} void work()
{
while(spfa()) //如果存在路径，则计算流量
{
int x = kk;
while(pre[x] != -)
{
flow[pre[x]][x] -= low[kk];
flow[x][pre[x]] += low[kk];
x = pre[x];
}
ans += dis[kk]; //计算距离和
}
} void outit()
{
printf("%d\n", ans);
} int main()
{
while(~scanf("%d%d", &n, &m) && (n+m))
{
init();
work();
outit();
}
return ;
}