打破无题解惨案。

这题就是二分图带权匹配。

可以发现一定是完备匹配，所以 KM 或 最小费用最大流 都是可以的。

下面是费用流的参考代码：（写的太丑，将就着看吧）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1010;
const int M = 200010;
const int INF = 0x3f3f3f3f;

int r, c, S, T, cnt, ans;
int head[N*2], d[N*2], pre[N*2], vis[N*2], incf[N*2];
char s[N][N];
struct node{int x, y;} a[N], b[N];
struct Edge{int nxt, to, val, cost;} ed[N*N];

void init(){
    cnt = 1; ans = 0;
    memset(head, 0, sizeof(head));
}

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

void add(int u, int v, int w, int c){
    ed[++ cnt] = (Edge){head[u], v, w, c}; head[u] = cnt;
    ed[++ cnt] = (Edge){head[v], u, 0, -c}; head[v] = cnt;
}

bool spfa(){
    queue<int> q;
    memset(vis, false, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    vis[S] = true, d[S] = 0, q.push(S);
    incf[S] = 1 << 30;
    while(!q.empty()){
        int u = q.front(); q.pop(); vis[u] = false;
        for(int i = head[u]; i; i = ed[i].nxt){
            int v = ed[i].to, w = ed[i].val, c = ed[i].cost;
            if(!w) continue;
            if(d[v] > d[u] + c){
                d[v] = d[u] + c;
                incf[v] = min(w, incf[u]);
                pre[v] = i;
                if(!vis[v]) q.push(v), vis[v] = true;
            }
        }
    }
    if(d[T] == INF) return false;
    return true;
}

void update(){
    int u = T;
    while(u != S){
        int i = pre[u];
        ed[i].val -= incf[T];
        ed[i ^ 1].val += incf[T];
        u = ed[i ^ 1].to;
    }
    ans += d[T] * incf[T];
}

int main(){
    while(~scanf("%d %d", &r, &c) && r){
        init();
        for(int i = 1; i <= r; i ++) scanf("%s", s[i] + 1);
        int tot1 = 0, tot2 = 0;
        for(int i = 1; i <= r; i ++)
            for(int j = 1; j <= c; j ++)
                if(s[i][j] == 'm') a[++ tot1] = (node){i, j};
                else if(s[i][j] == 'H') b[++ tot2] = (node){i, j};
        for(int i = 1; i <= tot1; i ++)
            for(int j = 1; j <= tot2; j ++)
                add(i, j + tot1, 1, abs(a[i].x - b[j].x) + abs(a[i].y - b[j].y));
        S = 0, T = tot1 * 2 + 1;
        for(int i = 1; i <= tot1; i ++) add(S, i, 1, 0);
        for(int i = tot1 + 1; i <= tot2 + tot1; i ++) add(i, T, 1, 0);
        while(spfa()) update();
        printf("%d\n", ans);
    }
    return 0;
}