重新切一遍最小费用最大流~~~
这到题目的数据范围有问题，尽量开大就好了~~
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
#define INF 999999
struct list
{int u;int v;int next;
}node[1000001];
int num;
int head[1001];
int cost[1001][1001];
void add(int l,int r,int v)
{node[num].u=r;node[num].v=v;node[num].next=head[l];head[l]=num++;
}
int nos;
int juli(int x,int y,int m)
{return abs(y/m-x/m)+abs(y%m-x%m);
}
int pre[1001];
int bfs()
{int visit[1001];int dist[1001];int i;for(i=0;i<=nos;i++)dist[i]=INF;memset(visit,0,sizeof(visit));memset(pre,-1,sizeof(pre));queue<int>q;q.push(0);visit[0]=1;dist[0]=0;while(!q.empty()){int e=q.front();q.pop();//cout<<"弹"<<" "<<e<<endl;visit[e]=0;for(i=head[e];i!=-1;i=node[i].next){int r=node[i].u;if(dist[e]+node[i].v<dist[r]&&cost[e][r]){pre[r]=e;dist[r]=dist[e]+node[i].v;// printf("pre[%d]=%d,dist[%d]=%d\n",r,e,r,dist[r]);if(!visit[r]){q.push(r);// cout<<"入"<<" "<<r<<endl;visit[r]=1;}}}}if(dist[nos]!=INF)return 1;return 0;
}
void change()
{int minx;minx=INF;int i;for(i=nos;pre[i]!=-1;i=pre[i]){minx=min(minx,cost[pre[i]][i]);}for(i=nos;pre[i]!=-1;i=pre[i]){cost[pre[i]][i]-=minx;cost[i][pre[i]]+=minx;}
}
int main()
{int i,j,m,n;char str[100001];while(scanf("%d%d%*c",&n,&m)&&(n||m)){memset(head,-1,sizeof(head));memset(cost,0,sizeof(cost));int hm,mm;hm=mm=0;int ms[100001];int hs[100001];for(i=0;i<n;i++){scanf("%s",str);for(j=0;j<m;j++){if(str[j]=='m')ms[++mm]=i*m+j;else if(str[j]=='H')hs[++hm]=i*m+j;}getchar();}nos=hm+mm+1;for(i=1;i<=mm;i++){add(0,i,0);add(i,0,0);cost[0][i]=1;cost[i][0]=0;}for(j=1;j<=hm;j++){add(j+mm,mm+hm+1,0);add(mm+hm+1,j+mm,0);cost[j+mm][mm+hm+1]=1;cost[mm+hm+1][j+mm]=0;}for(i=1;i<=mm;i++){for(j=1;j<=hm;j++){int ju=juli(ms[i],hs[j],m);add(i,j+mm,ju);add(j+mm,i,-ju);cost[i][j+mm]=INF;cost[j+mm][i]=0;}}while(bfs()){change();//cout<<"------------------------------------"<<endl;}int sum=0;for(i=1;i<=mm;i++)for(j=1;j<=hm;j++){sum+=(INF-cost[i][j+mm])*juli(ms[i],hs[j],m);}cout<<sum<<endl;}return 0;
}