最小费用最大流，即MCMF（Minimum Cost Maximum Flow）问题
嗯~第一次写费用流题。。。
这道就是费用流的模板题，找不到更裸的题了
建图：每个m(Man)作为源点，每个H(House)作为汇点，各个源点与汇点分别连一条边，这条边的流量是1（因为每个源点只能走一条边到汇点），费用是 从源点走到汇点的步数，因为有多个源点与汇点，要建一个超级源点与超级汇点，超级源点与各个源点连一条流量为1，费用为0（要避免产生多余的费用）的边
按照这个图跑一发费用流即可
关于模板：前向星+SPFA
初始化注意：size 表示网络中的结点数，编号从0开始，如果是从1开始则size=n+1，其他的，head全设为-1，Edge为边数预先设为0
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<string>
#include<sstream>
#define MAXN 3000
#define MAXM 50000
#define INF (1<<30)
#define eps 0.000001
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
using namespace std;
int i,j,k,n,m,x,y,T,num,w,Man,House,hou[305][2],man[305][2]; /*最小费用流模板 -BEGIN-*/
/*size表示网络中的结点数，编号从0开始，如果是从1开始则size=n+1*/
/*初始化：head全设为-1，Edge为边数预先设为0*/
int head[MAXN],vis[MAXN],dis[MAXN],pos[MAXN],Edge,size;
char s[305][305];
struct edgenode
{
int to,next,w,cost;
} edge[MAXM]; void add_edge(int x,int y,int w,int cost)
{
edge[Edge].to=y;
edge[Edge].w=w;
edge[Edge].cost=cost;
edge[Edge].next=head[x];
head[x]=Edge;
Edge++; edge[Edge].to=x;
edge[Edge].w=0;
edge[Edge].cost=-cost;
edge[Edge].next=head[y];
head[y]=Edge;
Edge++;
} bool SPFA(int s, int t)
{
int u,v,i;
queue <int> q;
memset(vis,0,sizeof(vis));
for(i=0;i<size;i++) dis[i]=INF;
dis[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
u=q.front(); q.pop(); vis[u]=0;
for (i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].to;
if(edge[i].w>0&&dis[u]+edge[i].cost<dis[v])
{
dis[v]=dis[u]+edge[i].cost;
pos[v]=i;
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
return dis[t]!=INF;
}
int MinCostFlow(int s,int t)
{
int i,cost=0,flow=0;
while(SPFA(s,t))
{
int d=INF;
for (i=t;i!=s;i=edge[pos[i]^1].to)
{
d=min(d,edge[pos[i]].w);
}
for(i=t;i!=s;i=edge[pos[i]^1].to)
{
edge[pos[i]].w-=d;
edge[pos[i]^1].w+=d;
}
flow+=d;
cost+=dis[t]*d;
}
return cost; // flow是最大流值
}
/*最小费用流模板 -END-*/
int main()
{
while(scanf("%d%d",&n,&m),n+m)
{
memset(head,-1,sizeof(head));
Edge=Man=House=num=0;
for (i=0;i<n;i++) scanf("%s",s[i]);
for (i=0;i<n;i++)
{
for (j=0;j<m;j++)
{
if (s[i][j]=='m')
{
Man++;
man[Man][0]=i;
man[Man][1]=j;
}else
if (s[i][j]=='H')
{
House++;
hou[House][0]=i;
hou[House][1]=j;
}
}
}
size=Man+House+2;
/*超级源点0，到各个人的边*/
for (i=1;i<=Man;i++)
{
add_edge(0,i,1,0);
}
/*各源点与各汇点之间的边*/
for (i=1;i<=Man;i++)
{
for (j=1;j<=House;j++)
{
add_edge(i,Man+j,1,abs(man[i][0]-hou[j][0])+abs(man[i][1]-hou[j][1]));
}
}
/*超级汇点0，到各个人的边*/
for (i=1;i<=House;i++)
{
add_edge(Man+i,Man+House+1,1,0);
}
printf("%d\n",MinCostFlow(0,Man+House+1));
}
return 0;
}
据说可以用KM算法来写，下次补上KM算法的代码。。。