终于切掉了我的第一道最小费用流了...
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define MN 222
using namespace std;struct Home{ int i,j; }H[MN];
struct Man{ int i,j; }M[MN];
struct Edge{ int u,v,c,f,next,cost; }E[MN*MN];int head[MN],dis[MN],cur[MN],pre[MN];
int s,t,aug,min,EN,cntH,cntM,ans;int mmin( int a,int b ){ return a<b?a:b; }void addEdge( int u,int v,int c,int cc,int cost )
{E[EN].v=v; E[EN].c=c; E[EN].f=0;E[EN].cost=cost; E[EN].next=head[u]; head[u]=EN++;E[EN].v=u; E[EN].c=cc; E[EN].f=0;E[EN].cost=-cost; E[EN].next=head[v]; head[v]=EN++;
}void spfa()
{bool vis[MN];queue<int>Q;memset( vis,0,sizeof(vis) );memset( dis,0x3f,sizeof(dis) );Q.push(s);dis[s]=0;pre[s]=s;while( !Q.empty() ){int cv=Q.front();Q.pop();vis[cv]=false;for( int i=head[cv];i!=-1;i=E[i].next ){if( dis[E[i].v]>dis[cv]+E[i].cost && E[i].f<E[i].c ){pre[E[i].v]=cv;cur[E[i].v]=i;dis[E[i].v]=dis[cv]+E[i].cost;if( !vis[E[i].v] ){vis[E[i].v]=true;Q.push(E[i].v);}}} }
}int main()
{char G[MN][MN];int n,m;while( scanf("%d %d",&n,&m)!=EOF ){if( n==0 && m==0 )break;cntH=cntM=0;ans=0;EN=0;memset( head,-1,sizeof(head) );for( int i=0;i<n;i++ )scanf( "%s",&G[i] );for( int i=0;i<n;i++ ) for( int j=0;j<m;j++ )if( G[i][j]=='m' ){ M[cntM].i=i; M[cntM++].j=j; }else if( G[i][j]=='H' ){ H[cntH].i=i; H[cntH++].j=j; }s=0;t=cntH+cntM+1;for( int i=0;i<cntH;i++ )for( int j=0;j<cntM;j++ )addEdge( i+1,cntH+j+1,1,0,abs(H[i].i-M[j].i)+abs(H[i].j-M[j].j) );for( int i=0;i<cntH;i++ )addEdge( s,i+1,1,0,0 );for( int i=0;i<cntM;i++ )addEdge( cntH+i+1,t,1,0,0 );while( true ){aug=0x3f3f3f3f;spfa();//printf( "%d\n",aug );if( dis[t]==0x3f3f3f3f )break;for( int i=t;i!=s;i=pre[i] )aug=mmin( aug,E[cur[i]].c-E[cur[i]].f );for( int i=t;i!=s;i=pre[i] ) E[cur[i]].f+=aug,E[cur[i]^1].f-=aug;ans+=aug*dis[t];}printf( "%d\n",ans );}return 0;
}