POJ2195 Going Home 最佳完美匹配

　　最佳完美匹配裸题，直接用KM算法求就可以了。

　　KM算法就是维护每个点的可行顶标，即始终有 l(x)+l(y)>=w(x,y)（求最大）、l(x)+l(y)<=w(x,y)（求最小），然后依次加边，求最大匹配，直到匹配是完美匹配即可。

  1 //STATUS:G++_AC_0MS_764KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 using namespace std;
 13 #define LL long long
 14 #define Max(a,b) ((a)>(b)?(a):(b))
 15 #define Min(a,b) ((a)<(b)?(a):(b))
 16 #define mem(a,b) memset(a,b,sizeof(a))
 17 #define lson l,mid,rt<<1
 18 #define rson mid+1,r,rt<<1|1
 19 const int MAX=110,INF=200000000;
 20 
 21 struct Node{
 22     int x,y;
 23 }H[MAX],M[MAX];
 24 
 25 char map[MAX][MAX];
 26 int w[MAX][MAX],lx[MAX],ly[MAX],S[MAX],T[MAX],y[MAX];
 27 int n,m,k1,k2;
 28 
 29 int dfs(int u)
 30 {
 31     S[u]=1;
 32     int v;
 33     for(v=0;v<k1;v++){
 34         if(w[u][v]==lx[u]+ly[v] && !T[v]){
 35             T[v]=1;
 36             if(y[v]==-1 || dfs(y[v])){
 37                 y[v]=u;
 38                 return 1;
 39             }
 40         }
 41     }
 42     return 0;
 43 }
 44 
 45 void update()
 46 {
 47     int i,j,min;
 48     min=INF;
 49     for(i=0;i<k1;i++)if(S[i])
 50         for(j=0;j<k1;j++)if(!T[j])
 51             min=Min(min,w[i][j]-lx[i]-ly[j]);
 52     for(i=0;i<k1;i++){
 53         if(S[i])lx[i]+=min;
 54         if(T[i])ly[i]-=min;
 55     }
 56 }
 57 
 58 void KM()
 59 {
 60     mem(y,-1);
 61     mem(ly,0);
 62     int i,j;
 63     for(i=0;i<k1;i++){
 64         lx[i]=INF;
 65         for(j=0;j<k1;j++)
 66             if(w[i][j]<lx[i])lx[i]=w[i][j];
 67     }
 68     for(i=0;i<k1;i++){
 69         while(1){
 70             mem(S,0);mem(T,0);
 71             if(dfs(i))break;
 72             update();
 73         }
 74     }
 75 }
 76 
 77 int main()
 78 {
 79 //    freopen("in.txt","r",stdin);
 80     int i,j,ans;
 81     while(~scanf("%d%d",&n,&m) && n&&m)
 82     {
 83         ans=k1=k2=0;
 84         mem(w,0);
 85         for(i=0;i<n;i++){
 86             scanf("%s",map[i]);
 87             for(j=0;j<m;j++){
 88                 if(map[i][j]=='m')
 89                     M[k1].x=i,M[k1++].y=j;
 90                 if(map[i][j]=='H')
 91                     H[k2].x=i,H[k2++].y=j;
 92             }
 93         }
 94         for(i=0;i<k1;i++)
 95             for(j=0;j<k1;j++)
 96                 w[i][j]=abs(M[i].x-H[j].x)+abs(M[i].y-H[j].y);
 97 
 98         KM();
 99         for(i=0;i<k1;i++)
100             ans+=w[y[i]][i];
101 
102         printf("%d\n",ans);
103     }
104 }