hdu 1533(最小权匹配）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1533

题意：

给你一个N行M列的矩阵，其中“.”代表空地，“H”代表房子，“m”代表人，其中有n个房子和n个人。现在要求每个人进入一间房子，且人走一步需要支付1美元。

求最小需要花费多少美元才能让所有人都进入到房子中（每个人只能进入一间房子，每个房子只能容纳一个人）。

思路：就是一个二分图最优匹配的变形，所以说建图很重要啊！！！(把‘m'的坐标计入到X集，’H‘的坐标计入到Y集）在建图的时候，将每条边的权值变为负数。然后lx[i]初始化为-inf，结果输出-ans，就可以得到最小权值

View Code

  1 #include<iostream>
  2 const int MAXN=110;
  3 const int inf=1<<30;
  4 using namespace std;
  5 char G[MAXN][MAXN];
  6 int map[MAXN][MAXN];
  7 int lx[MAXN],ly[MAXN];
  8 int match[MAXN];
  9 bool visitx[MAXN],visity[MAXN];
 10 int n;
 11 
 12 int Hungary(int u){
 13     visitx[u]=true;
 14     for(int i=0;i<n;i++){
 15         if(!visity[i]&&lx[u]+ly[i]==map[u][i]){
 16             visity[i]=true;
 17             if(match[i]==-1||Hungary(match[i])){
 18                 match[i]=u;
 19                 return true;
 20             }
 21         }
 22     }
 23     return false;
 24 }
 25 
 26 void KM_prefect_match(){
 27     int tmp;
 28     //注意，此时要初始化为无穷小
 29     for(int i=0;i<n;i++){
 30         lx[i]=-inf;
 31     }
 32     memset(ly,0,sizeof(ly));
 33     for(int i=0;i<n;i++){
 34         for(int j=0;j<n;j++){
 35             lx[i]=max(lx[i],map[i][j]);
 36         }
 37     }
 38     for(int i=0;i<n;i++)
 39     {
 40         while(1){
 41             memset(visitx,false,sizeof(visitx));
 42             memset(visity,false,sizeof(visity));
 43             if(Hungary(i))//匹配成功
 44                 break;
 45             else {
 46                 tmp=inf;
 47                 for(int j=0;j<n;j++)if(visitx[j]){//x在交错树中
 48                     for(int k=0;k<n;k++){
 49                         //y在交错树外
 50                         if(!visity[k]&&tmp>lx[j]+ly[k]-map[j][k]){
 51                             tmp=lx[j]+ly[k]-map[j][k];
 52                         }
 53                     }
 54                 }
 55                 //更新顶标
 56                 for(int j=0;j<n;j++){
 57                     if(visitx[j])
 58                         lx[j]-=tmp;
 59                     if(visity[j])
 60                         ly[j]+=tmp;
 61                 }
 62             }
 63         }
 64     }
 65 }
 66 
 67 int main(){
 68     int row,col;
 69     while(~scanf("%d%d",&row,&col)){
 70         if(row==0&&col==0)break;
 71         n=0;
 72         int cnt1=0,cnt2=0;
 73         memset(map,0,sizeof(map));
 74         memset(match,-1,sizeof(match));
 75         for(int i=0;i<row;i++){
 76             scanf("%s",G[i]);
 77             for(int j=0;j<col;j++){
 78                 if(G[i][j]=='m')n++;
 79             }
 80         }
 81         //建图很重要！！！
 82         for(int i=0;i<row;i++){
 83             for(int j=0;j<col;j++){
 84                 if(G[i][j]=='m'){
 85                     for(int k=0;k<row;k++){
 86                         for(int l=0;l<col;l++){
 87                             if(G[k][l]=='H'){
 88                                 map[cnt1][cnt2++]=-1*(abs(i-k)+abs(j-l));//由于求得是最小权值和，取相反数
 89                             }
 90                         }
 91                     }
 92                     cnt1++;
 93                     cnt2=0;
 94                 }
 95             }
 96         }
 97         KM_prefect_match();
 98         int ans=0;
 99         for(int i=0;i<n;i++){
100             ans+=map[match[i]][i];
101         }
102         printf("%d\n",-ans);//最后取相反数就行了
103     }
104     return 0;
105 }