费用流模板（带权二分图匹配）——hdu1533

/*

带权二分图匹配

用费用流求，增加源点s 和 汇点t

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 10005

#define maxm 200005

struct Edge{int to,nxt,w,c;}e[maxm<<];

int head[maxn],tot,n,m,s,t,ans,maxflow;

char mp[maxn][maxn];

vector<pair<int,int> >M,H;

void add(int u,int v,int w,int c){

    e[tot].to=v;e[tot].w=w;e[tot].c=c;e[tot].nxt=head[u];head[u]=tot++;

    e[tot].to=u;e[tot].w=;e[tot].c=-c;e[tot].nxt=head[v];head[v]=tot++;

}

int d[maxn],v[maxn],incf[maxn],pre[maxn];

bool spfa(){

    queue<int>q;

    memset(d,0x3f,sizeof d);

    memset(v,,sizeof v);

    q.push(s);d[s]=;v[s]=;

    incf[s]=<<;

    while(q.size()){

        int x=q.front();q.pop();v[x]=;

        for(int i=head[x];i!=-;i=e[i].nxt){

            int y=e[i].to;

            if(e[i].w==)continue;

            if(d[y]>d[x]+e[i].c){

                d[y]=d[x]+e[i].c;

                incf[y]=min(incf[x],e[i].w);

                pre[y]=i;

                if(!v[y])v[y]=,q.push(y);

            }

        }

    }

    if(d[t]==0x3f3f3f3f)return false;

    return true;

}

void update(){

    int x=t;

    while(x!=s){

        int i=pre[x];

        e[i].w-=incf[t];

        e[i^].w+=incf[t];

        x=e[i^].to;

    }

    maxflow+=incf[t];

    ans+=d[t]*incf[t];

}

void init(){

    memset(head,-,sizeof head);

    tot=ans=maxflow=;

    M.clear();H.clear();

}

int dis(pair<int,int> a,pair<int,int> b){

    return abs(a.first-b.first)+abs(a.second-b.second);

}

int main(){

    while(cin>>n>>m&&n){

        init();

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++){

                scanf("\n%c",&mp[i][j]);

                if(mp[i][j]=='m')

                    M.push_back(make_pair(i,j));

                if(mp[i][j]=='H')

                    H.push_back(make_pair(i,j));

            }

        s=,t=*M.size()+;

        for(int i=;i<M.size();i++)

            add(s,i+,,);

        for(int i=;i<H.size();i++)

            add(i++M.size(),t,,);

        for(int i=;i<M.size();i++)

            for(int j=;j<H.size();j++)

                add(i+,j++M.size(),,dis(M[i],H[j]));

        while(spfa())

            update();

        cout<<ans<<'\n';

    }

}