這是一個典型的最大匹配的題目，題目意思是給出一些房子和一些人，每個人到每個房子都有一個相應的代價，最后要求怎么安排這些人，房子和人一一配對，使最后的代價最小。
方法是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;
}