KM poj 2195

题意：给出一个地图，地图上有人和房子，问如何分配哪个人去哪个房子，走的路最短？

这道题是个完备匹配的情况下，问怎么才能走的路最少，可以用KM来做。

只不过KM算法是用来求解最大最优值，所以我们得改一下数据，将每个人去房子的路程都改为负数。

最后再得出 -KM（）即刻

 #include<cstdio>

 #include<algorithm>

 #include<string.h>

 #include<math.h>

 #include<iostream>

 using namespace std;

 const int maxn=1e2+;

 const int inf=0x3f3f3f3f;

 int lx[maxn],ly[maxn];

 int match[maxn];

 int visx[maxn],visy[maxn];

 struct node

 {

     int x,y;

 }a[maxn],b[maxn];

 int G[maxn][maxn];

 int numa,numb;

 int dfs(int k)

 {

     visx[k]=;

     for(int i=;i<=numa;i++){

         if(!visy[i]&&G[k][i]==lx[k]+ly[i]){

             visy[i]=;

             if(!match[i]||dfs(match[i])){

                 match[i]=k;

                 return ;

             }

         }

     }

     return ;

 }

 int KM()

 {

     for(int i=;i<=numa;i++){

         lx[i]=-inf,ly[i]=;

         for(int j=;j<=numa;j++)

             lx[i]=max(lx[i],G[i][j]);

     }

     for(int k=;k<=numa;k++){

         while(){

             memset(visx,,sizeof(visx));

             memset(visy,,sizeof(visy));

             if(dfs(k)) break;

             int mn=inf;

             for(int i=;i<=numa;i++) if(visx[i])

             for(int j=;j<=numa;j++) if(!visy[j])

             mn=min(mn,lx[i]+ly[j]-G[i][j]);

             if(mn==inf) return -;

             for(int i=;i<=numa;i++) if(visx[i]) lx[i]-=mn;

             for(int i=;i<=numa;i++) if(visy[i]) ly[i]+=mn;

         }

     }

     int ans=;

     for(int i=;i<=numa;i++)

     if(match[i])

     ans+=G[match[i]][i];

     return ans;

 }

 void init()

 {

     numa=numb=;

     memset(match,,sizeof(match));

     memset(G,,sizeof(G));

 }

 int main()

 {

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF){

         if(n==&&m==) break;

         init();

         char t;

         for(int i=;i<n;i++){

             for(int j=;j<m;j++){

                 cin>>t;

                 if(t=='H'){

                     numa++;

                     a[numa].x=i;

                     a[numa].y=j;

                 }

                 else if(t=='m'){

                     numb++;

                     b[numb].x=i;

                     b[numb].y=j;

                 }

             }

         }

         for(int i=;i<=numa;i++){

             int x1=a[i].x,y1=a[i].y;

             for(int j=;j<=numb;j++){

                 int x2=b[j].x,y2=b[j].y;

                 int w=fabs(x1-x2)+fabs(y1-y2);

                 G[i][j]=-w;

             }

         }

         printf("%d\n",-KM());

     }

     return ;

 }