HDUnbsp;1533nbsp;Goingnbsp;Homenbsp;（KM算法）

本文主要是介绍HDUnbsp;1533nbsp;Goingnbsp;Homenbsp;（KM算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

这个题也是KM算法，详解见上一篇文章，但是需要转化为KM模型，求出所有men到所有House的花费，构建成一个图，然后用KM就可以解了

代码：

C语言: 高亮代码由发芽网提供

 #include<stdio.h> 
 #include<string.h> 
 #include<math.h> 
 #define M 110 
 #define MAX(a,b) a>b?a:b 
 #define MIN(a,b) a>b?b:a 
 
 char map [ M ][ M ]; 
 int num [ M ][ M ], match [ M ]; 
 int w [ M ][ M ], lx [ M ], ly [ M ], sx [ M ], sy [ M ]; 
 int m ,n; 
 
 struct point { 
       int x , y; 
 } men [ M ], house [ M ]; 
 
 int search( int u) 
 { 
       int j; 
       sx [ u ] = 1; 
       for( j = 1; j <=n; j ++) 
             if( ! sy [ j ] && w [ u ][ j ] == lx [ u ] + ly [ j ]) 
             { 
                   sy [ j ] = 1; 
                   if( ! match [ j ] || search( match [ j ])) 
                   { 
                         match [ j ] = u; 
                         return 1; 
                   } 
             } 
             return 0; 
 } 
 
 void KM_match() 
 { 
       int i , j , k , min; 
       for( i = 1; i <=n; i ++) 
       { 
             lx [ i ] = w [ i ][ 1 ]; 
             for( j = 2; j <=n; j ++) 
                   lx [ i ] = MAX( lx [ i ], w [ i ][ j ]); 
       } 
       memset( ly , 0 , sizeof( ly)); 
       memset( match , 0 , sizeof( match)); 
       for( i = 1; i <=n; i ++) 
       { 
             while( 1) 
             { 
                   memset( sx , 0 , sizeof( sx)); 
                   memset( sy , 0 , sizeof( sy)); 
                   if( search( i)) break; 
                   min = 2147483647; 
                   for( j = 1; j <=n; j ++) 
                         if( sx [ j ]) 
                         { 
                               for( k = 1; k <=n; k ++) 
                                     if( ! sy [ k ]) 
                                        min = MIN( min , lx [ j ] + ly [ k ] - w [ j ][ k ]); 
                         } 
                   for( j = 1; j <=n; j ++) if( sx [ j ]) lx [ j ] -= min; 
                   for( j = 1; j <=n; j ++) if( sy [ j ]) ly [ j ] += min; 
             } 
 
       } 
 } 
 
 int main() 
 { 
       int i , j , flag1 , flag2 , sum; 
       while( scanf( "%d%d" , & m , &n ), m||n) 
       { 
             memset( num , 0 , sizeof( num)); 
             flag1 = flag2 = 0; 
             for( i = 0; i < m; i ++) 
             { 
                   scanf( "%s" , map [ i ]); 
                   for( j = 0; map [ i ][ j ]; j ++) 
                         if( map [ i ][ j ] == 'm' ){ flag1 ++; men [ flag1 ]. x = i; men [ flag1 ]. y = j ;} 
                         else if( map [ i ][ j ] == 'H' ){ flag2 ++; house [ flag2 ]. x = i; house [ flag2 ]. y = j ;} 
             } 
             for( i = 1; i <= flag1; i ++) 
                   for( j = 1; j <= flag2; j ++) 
                         w [ i ][ j ] =-( abs( men [ i ]. x - house [ j ]. x) + abs( men [ i ]. y - house [ j ]. y)); 
            n = flag1; 
             KM_match(); 
             sum = 0; 
             for( i = 1; i <=n; i ++) sum += w [ match [ i ]][ i ]; 
             printf( "%d \n " , - sum); 
       } 
       return 0; 
 } 
 