就是最基本的二分图最优匹配，将每个人向每个房子建一条边，权值就是他们manhattan距离。然后对所有权值取反，求一次最大二分图最优匹配，在将结果取反就行了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define Maxn 110 using namespace std; int n;//点的数目 int lx[Maxn],ly[Maxn]; //顶点标号 int weight[Maxn][Maxn];// 边的权值 int slack[Maxn];// Y(i)的松弛函数 int sx[Maxn],sy[Maxn]; //标记X,Y中的顶点是否在交错路径上 int match[Maxn];//Y的匹配 struct Point{ int x,y; }house[Maxn],man[Maxn]; int Dis(Point a,Point b) { return abs(a.x-b.x)+abs(a.y-b.y); } int dfs(int u) { sx[u]=1; int i; for(i=1;i<=n;i++) { if(!sy[i]&&lx[u]+ly[i]==weight[u][i])//如果在相等子图中，且未被访问 { sy[i]=1; if(match[i]==-1||dfs(match[i])) { match[i]=u; return 1; } } else if(!sy[i])//Y(i)不在交错路径当中 slack[i]=min(slack[i],lx[u]+ly[i]-weight[u][i]); } return 0; } int bestmatch(bool f) { int i,j; if(!f) { for(i=1;i<=n;i++) { lx[i]=-0x7FFFFFFF; ly[i]=0; for(j=1;j<=n;j++) { weight[i][j]=-weight[i][j]; lx[i]=max(lx[i],weight[i][j]); } } } else { for(i=1;i<=n;i++) { lx[i]=0; ly[i]=0; for(j=1;j<=n;j++) lx[i]=max(lx[i],weight[i][j]); } } memset(match,-1,sizeof(match)); for(i=1;i<=n;i++) while(1) { memset(sx,0,sizeof(sx)); memset(sy,0,sizeof(sy)); for(j=0;j<=Maxn-1;j++) slack[j]=0x7FFFFFFF; if(dfs(i)) break; int dx=0x7FFFFFFF; for(j=1;j<=n;j++) dx=min(dx,slack[j]); for(j=1;j<=n;j++) { if(sx[j]) lx[j]-=dx; if(sy[j]) ly[j]+=dx; } } int ans=0; for(i=1;i<=n;i++) ans+=weight[match[i]][i]; if(!f) ans=-ans; return ans; } int main() { int i,j,N,M,a,b; char str[110]; while(scanf("%d%d",&N,&M),N||M) { a=b=0; for(i=1;i<=N;i++) { scanf("%s",&str); for(j=0;j<M;j++) { if(str[j]=='H') house[++a].x=i,house[a].y=j; if(str[j]=='m') man[++b].x=i,man[b].y=j; } } n=a; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) weight[i][j]=Dis(man[i],house[j]); } printf("%d ",bestmatch(false)); } return 0; }
最小费油最大流解法：
#include<iostream> #include<cstring> #include<cstring> using namespace std; const int size = 1010; const int INF = 0x7fffffff; struct Point{ int x,y; }; struct Edge { int to; int vol; int cost; int next; }e[size*100]; Point house[110],man[110]; int index[size]; int edgeNum; int pre[size], pos[size]; int dis[size], que[size*10]; bool vis[size]; void insert(int from, int to, int vol, int cost) { e[edgeNum].to = to; e[edgeNum].vol = vol; e[edgeNum].cost = cost; e[edgeNum].next = index[from]; index[from] = edgeNum++; e[edgeNum].to = from; e[edgeNum].vol = 0; e[edgeNum].cost = -cost; e[edgeNum].next = index[to]; index[to] = edgeNum++; } int DIS(Point p1,Point p2) { return abs(p1.x-p2.x)+abs(p1.y-p2.y); } bool spfa(int s, int t) { int i; memset(pre, -1, sizeof(pre)); memset(vis, 0, sizeof(vis)); int head, tail; head = tail = 0; for(i = 0; i < size; i++) dis[i] = INF; que[tail++] = s; pre[s] = s; dis[s] = 0; vis[s] = 1; while(head != tail) { int now = que[head++]; vis[now] = 0; for(i = index[now]; i != -1; i = e[i].next) { int adj = e[i].to; if(e[i].vol > 0 && dis[now] + e[i].cost < dis[adj]) { dis[adj] = dis[now] + e[i].cost; pre[adj] = now; pos[adj] = i; if(!vis[adj]) { vis[adj] = 1; que[tail++] = adj; } } } } return pre[t] != -1; } int MinCostFlow(int s, int t, int flow) { int i; int cost = 0; flow = 0; while(spfa(s, t)) { int f = INF; for(i = t; i != s; i = pre[i]) if (e[pos[i]].vol < f) f = e[pos[i]].vol; flow += f; cost += dis[t] * f; for(i = t; i != s; i = pre[i]) { e[pos[i]].vol -= f; e[pos[i] ^ 1].vol += f; } } return cost; // flow是最大流值 } int main() { int n,m,i,j,u,v; char c; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; memset(index,-1,sizeof(index)); int k1=0,k2=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>c; switch(c) { case '.':break; case 'm':man[++k1].x=i,man[k1].y=j;break; case 'H':house[++k2].x=i,house[k2].y=j;break; } } } for(i=1;i<=k1;i++) { for(j=1;j<=k2;j++) { insert(i,j+k1,1,DIS(man[i],house[j])); } insert(0,i,1,0); insert(i+k1,k1+k2+1,1,0); } //spfa(0,k1+k2+1); int ans=MinCostFlow(0,k1+k2+1,0); printf("%d ",ans); } return 0; }