这是一个典型的最大匹配的题目，题目意思是给出一些房子和一些人，每个人到每个房子都有一个相应的代价，最后要求怎么安排这些人，房子和人一一配对，使最后的代价最小。
方法是KM算法，是一个求最大（最小)匹配的一个很强大的算法。不过这种题目还可以用费用流来做。
下面是某牛的对KM算法讲解
http://hi.baidu.com/anonympine/blog/item/3ee64954fe6f6256574e0021.html
KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[i]，顶点Yi的顶标为B[i]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[i]+B[j]>=w[i,j]始终成立。KM算法的正确性基于以下定理：
若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。
这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。
初始时为了使A[i]+B[j]>=w[i,j]恒成立，令A[i]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。
我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：
- 两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。
- 两端都不在交错树中的边(i,j)，A[i]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。
- X端不在交错树中，Y端在交错树中的边(i,j)，它的A[i]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。
- X端在交错树中，Y端不在交错树中的边(i,j)，它的A[i]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。
现在的问题就是求d值了。为了使A[i]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于min{A[i]+B[j]-w[i,j]|Xi在交错树中，Yi不在交错树中}。
以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)
的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图
中，则让slack[j]变成原值与A[i]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小
值作为d值即可。但还要注意一点：修改顶标后，要把所有的slack值都减去d。
Source Code
| Problem: 2195 |
|
User: lovecanon |
| Memory: 368K |
|
Time: 0MS |
| Language: G++ |
|
Result: Accepted |
下面是2195我的代码：
//algorithm:KM O(n^4)
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
struct node{
int r,c;
}man[10001],home[10001];
int r,c,num_of_man,num_of_home,map[101][101],lx[101],ly[101],match[101];
bool visx[101],visy[101];
int dfs(int t){//寻找完备匹配
int i,tmp;
visx[t]=true;
for(i=1;i<=num_of_home;i++){
if(!visy[i] && lx[t]+ly[i]==map[t][i]){
tmp=match[i];
visy[i]=true;
match[i]=t;
if(tmp==0 || dfs(tmp)) return 1;
match[i]=tmp;
}
}
return 0;
}
int main(){
while(scanf("%d%d",&r,&c),r&&c){
getchar();
int i,j,k; char a;
num_of_home=0;num_of_man=0;
for(i=1;i<=r;i++){//read_data
for(j=1;j<=c;j++){
if((a=getchar())=='m'){
man[++num_of_man].r=i;
man[num_of_man].c=j;
}
else if(a=='H'){
home[++num_of_home].r=i;
home[num_of_home].c=j;
}
}
getchar();
}
//printf("%d %d\n",num_of_man,num_of_home);
memset(map,0,sizeof(map));
for(i=1;i<=num_of_man;i++){
for(j=1;j<=num_of_home;j++){
map[i][j]=(int )fabs(man[i].r-home[j].r)+(int )fabs(man[i].c-home[j].c);
}
}
memset(lx,127,sizeof(lx));
memset(ly,0,sizeof(ly));
for(i=1;i<=num_of_man;i++){
for(j=1;j<=num_of_home;j++){
if(map[i][j]<lx[i]) lx[i]=map[i][j];//如果是最大权值匹配 则初始值顶标取最大值
} //若是最小匹配则取最小值
}
//KM algorithm
memset(match,0,sizeof(match));
for(i=1;i<=num_of_man;i++){//
while(1){
memset(visx,0,sizeof(visx));//清零
memset(visy,0,sizeof(visy));
int min=10000000;
if(dfs(i)) break;//寻找完备匹配
for(j=1;j<=num_of_man;j++){//找出 min=1000000;x搜索树上y不在搜索树上边
if(visx[j]) //找出顶标最大能改进的d值
for(k=1;k<=num_of_home;k++){
if(!visy[k] && map[j][k]-lx[j]-ly[k]<min)//基于 lx[i]+ly[j]<=map[i][j] 找出map[j][k]-lx[j]-ly[k]的最小值 d
min=map[j][k]-lx[j]-ly[k]; //若是最大匹配则应满足 lx[i]+ly[j]>=map[i][j] 找出
} //lx[i]-ly[j]-map[i][j]的最小值 d
}
for(j=1;j<=num_of_man;j++) if(visx[j]) lx[j]+=min;//用d来改进搜索树上各点的顶标
for(j=1;j<=num_of_home;j++) if(visy[j]) ly[j]-=min; //
}
}
int sum=0;
for(i=1;i<=num_of_home;i++) sum+=map[match[i]][i];
printf("%d\n",sum);
}
return 0;
}