这题也可以用km做，我写的代码km比费用流快很多。
最小费用流:
#include<stdio.h> #include<string.h> #include<math.h> #include<queue> #include<stdlib.h> #define INF 1000000000 using namespace std; const int maxn = 1100; struct Set { int x,y; }mnum[110*110],hnum[110*110]; struct node { int to; int v; int flag; int cost; int next; }edge[maxn*maxn/2]; char map[110][110]; int n,m,cou1,cou2,index,head[maxn],s,t,pre[maxn],fpre[maxn],N,dis[maxn]; int Get(int i,int j) { return abs(mnum[i].x-hnum[j].x)+abs(mnum[i].y-hnum[j].y); } void add(int x,int y,int v,int cost) { edge[index].to=y; edge[index].v=v; edge[index].cost=cost; edge[index].flag=index+1; edge[index].next=head[x]; head[x]=index++; edge[index].to=x; edge[index].v=0; edge[index].cost=-cost; edge[index].flag=index-1; edge[index].next=head[y]; head[y]=index++; } void makemap() { int i,j; cou1=cou2=0; for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(map[i][j]=='m') { mnum[++cou1].x=i; mnum[cou1].y=j; } else if(map[i][j]=='H') { hnum[++cou2].x=i; hnum[cou2].y=j; } } } index=1; memset(head,-1,sizeof(head)); N=cou1+cou2+1; s=0; t=cou1+cou2+1; for(i=1;i<=cou1;i++) add(s,i,1,0); for(i=1;i<=cou2;i++) add(i+cou1,t,1,0); for(i=1;i<=cou1;i++) { for(j=1;j<=cou2;j++) { add(i,j+cou1,1,Get(i,j)); } } } bool spfa(int s,int t) { int vis[maxn]; queue<int>q; memset(pre,-1,sizeof(pre)); memset(vis,0,sizeof(vis)); int i; for(i=0;i<=N;i++) dis[i]=INF; vis[s]=1; dis[s]=0; pre[s]=0; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(i=head[u];i!=-1;i=edge[i].next) { if(edge[i].v&&dis[edge[i].to]>dis[u]+edge[i].cost) { dis[edge[i].to]=dis[u]+edge[i].cost; if(!vis[edge[i].to]) { vis[edge[i].to]=1; q.push(edge[i].to); } pre[edge[i].to]=u; fpre[edge[i].to]=i; } } } if(dis[t]>=INF)return false; return true; } int main() { int i,j; while(~scanf("%d%d",&n,&m)) { if(!n&&!m)break; for(i=0;i<n;i++) scanf("%s",map[i]); makemap(); int ans=0; while(spfa(s,t)) { int minflow=INF; for(i=t;i!=0;i=pre[i]) { if(minflow>edge[fpre[i]].v) minflow=edge[fpre[i]].v; } ans+=minflow*dis[t]; for(i=t;i!=0;i=pre[i]) { edge[fpre[i]].v-=minflow; edge[edge[fpre[i]].flag].v+=minflow; } } printf("%d ",ans); } }
km:
#include<stdio.h> #include<string.h> #include<algorithm> #define INF 99999999 #define maxn 105 using namespace std; struct node { int x; int y; }h[maxn],m[maxn]; char g[maxn][maxn]; int map[maxn][maxn],pr[maxn],pl[maxn],visr[maxn],visl[maxn],match[maxn],slack[maxn]; int col,row; void init(int x) { int i,j; for(i=0;i<=x;i++) for(j=0;j<=x;j++) if(i==j)map[i][j]=0; else map[i][j]=INF; } int dfs(int u,int n) { int i,j; visl[u]=1; for(i=0;i<n;i++) { if(!visr[i]) { int val=pl[u]+pr[i]-map[u][i]; if(val==0) { visr[i]=1; if(match[i]==-1||dfs(match[i],n)) { match[i]=u; return 1; } } if(val>0&&val<slack[i]) slack[i]=val; } } return 0; } int km(int n) { int i,j; memset(pr,0,sizeof(pr)); memset(match,-1,sizeof(match)); for(i=0;i<n;i++) pl[i]=INF; for(i=0;i<n;i++) { for(j=0;j<n;j++) slack[j]=INF; while(1) { memset(visr,0,sizeof(visr)); memset(visl,0,sizeof(visl)); if(dfs(i,n))break; int k=INF; for(j=0;j<n;j++) { if(!visr[j]&&slack[j]<k) k=slack[j]; } for(j=0;j<n;j++) { if(visl[j]) pl[j]-=k; if(visr[j]) pr[j]+=k; } } } int res=0; for(i=0;i<n;i++) { res+=map[match[i]][i]; } return res; } int main() { int i,j; while(scanf("%d%d",&row,&col)!=EOF) { if(row==0&&col==0) break; int count1=0,count2=0; for(i=0;i<row;i++) scanf("%s",g[i]); for(i=0;i<row;i++) for(j=0;j<col;j++) { if(g[i][j]=='H') { h[count1].x=i;h[count1++].y=j; } else if(g[i][j]=='m') { m[count2].x=i;m[count2++].y=j; } } init(count1); for(i=0;i<count1;i++) for(j=0;j<count2;j++) { map[i][j]=-(abs(h[i].x-m[j].x)+abs(h[i].y-m[j].y)); } printf("%d ",-km(count1)); } }