题目链接：https://cn.vjudge.net/problem/HDU-1533

题意:给你n个房子n个人  使得所有人都有一座房子的最小花费

思路：把所有的人与房子建边，最后，源点与所有的人建边，所有的房子与汇点，跑一边最消费用最大流即可

 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
#define ll long long
#define INF 0x3f3f3f3f
const int maxn = 1e5+5;

using namespace std;

struct node{
    int to;
    int c;
    int cost;
    int next;
}e[maxn];

struct point {
    int x,y;
    point(){}
    point(int a,int b):x(a),y(b){}
};
vector<point> v1,v2;

int head[maxn],cnt,l,r,n,m;

bool vis[maxn];
int dis[maxn],pre[maxn];

void init() {
    v1.clear();v2.clear();
    memset(head,-1,sizeof(head));
    cnt=0;
}

void insert(int u,int v,int c,int w) {
    e[cnt].to = v;
    e[cnt].c = c;
    e[cnt].cost = w;
    e[cnt].next = head[u];
    head[u] = cnt++;
}
void addedge(int u,int v,int c,int w){
    insert(u,v,c,w);
    insert(v,u,0,-w);
}

char a[105][105];
void build() {
    init();
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++) {
        if(a[i][j]=='m')
            v1.push_back(point(i,j));
        else if(a[i][j]=='H')
            v2.push_back(point(i,j));
    }
    l = v1.size();
    r = v2.size();
    for(int i=0;i<l;i++) {
        point P = v1[i];
        int x = i+1;
        addedge(0,x,1,0);
        for(int j=0;j<r;j++) {
            point H = v2[j];
            int y = j+l+1;
            int d = abs(P.x-H.x) + abs(P.y-H.y);
            addedge(x,y,1,d);
            if(i==l-1) {
                addedge(y,l+r+1,1,0);
            }
        }
    }
}
bool SPFA(int s,int t) {
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    dis[s]=0;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for(int i = head[x];i!=-1;i = e[i].next) {
            int to = e[i].to;
            if(e[i].c && dis[to] > dis[x] + e[i].cost){
                dis[to] = dis[x] + e[i].cost;
                pre[to] = i;
                if(!vis[to]) {
                    vis[to] = 1;
                    q.push(to);
                }
            }

        }
    }
    return pre[t] != -1;
}
int minCostMaxFLow(int s,int t) {
    int ans = 0;
    while(SPFA(s,t)) {
        int flow = INF;
        for(int i = t; i != s; i = e[pre[i]^1].to) {
            flow = min(flow, e[pre[i]].c);
            //cout<<flow<<endl;
        }
        for(int i=t;i!=s;i = e[pre[i]^1].to) {
            e[pre[i]].c-=flow;
            e[pre[i]^1].c+=flow;
            ans += e[pre[i]].cost*flow;
        }
    }

    return ans;
}
int main()
{
    while(scanf("%d%d",&n,&m) &&n&&m) {
        for(int i=0;i<n;i++)
            scanf("%s",a[i]);
        build();
        printf("%d\n",minCostMaxFLow(0,l+r+1));
    }
    return 0;
}