2520291_ac_15ms_208k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include "stdio.h"
#include "string.h"
#define INF 100000000
struct pos{
       int x;
       int y;       
}house[ 100 ], man[ 100 ];
int n, link[ 100 ], map[ 100 ][ 100 ], vx[ 100 ], vy[ 100 ], edge[ 100 ][ 100 ];

int main(){
    int N, M, i, j, h, m, t, cost;
    char c;
    void KM_Perfect_link();
    
    while( 1 ){
           scanf("%d %d", &N, &M);
           if ( N == 0 ){
                break;     
           }       
           
           h = 0;
           m = 0;
           
           getchar();
           for ( i = 1; i <= N; i++ ){
                 for ( j = 1; j <= M; j++ ){
                       scanf("%c", &c);
                       if ( c == 'H' ){
                            house[ h ].x = i;
                            house[ h ].y = j;
                            h ++;
                       }else if ( c == 'm' ){
                            man[ m ].x = i;
                            man[ m ].y = j;
                            m ++;      
                       }
                 }
                 getchar();
           }
           n = h;
           
           for ( i = 0; i < n; i++ ){
                 for ( j = 0; j < n; j++ ){
                       t = man[ i ].x - house[ j ].x;
                       t = t < 0 ? -t : t;
                       edge[ i ][ j ] = t;
                       t = man[ i ].y - house[ j ].y;
                       t = t < 0 ? -t : t;
                       edge[ i ][ j ] += t;
                       
                 }
           }
           KM_Perfect_link(); 
           cost = 0;
           for ( i = 0; i < n; i ++ ){
                 cost += edge[ link[ i ] ][ i ];
           }
           
           printf("%d\n", cost );
    }
    return 0;
}
int dfs(int);
void KM_Perfect_link(){
     int i, j, live, min, t;
     int lx[ 100 ], ly[ 100 ];
     int perfect;
     for ( i = 0; i < n; i++ ){
         lx[ i ] = 0;
         ly[ i ] = INF;
         for ( j = 0; j < n; j++ ){
               ly[ i ] = edge[ j ][ i ] < ly[ i ] ? edge[ j ][ i ] : ly[ i ];
         }    
     }
     
     perfect = 0;
     while ( !perfect ){
           for ( i = 0; i < n; i++ ){
                 for ( j = 0; j < n; j ++ ){
                       if ( lx[ i ] + ly[ j ] == edge[ i ][ j ] ){
                            map[ i ][ j ] = 1;   
                       }else{
                            map[ i ][ j ] = 0;      
                       }     
                 }
           }   
           
           live = 0; 
           memset( link, -1, sizeof( link ) );
           for ( i = 0; i < n; i++ ){
               memset( vx, 0, sizeof( link ) );
               memset( vy, 0, sizeof( link ) );
               if ( dfs( i ) ){
                    live ++;   
               }else{
                    vx[ i ] = 1;
                    break;      
               }
           }
           
           if ( live == n ){
                perfect = 1;
           }
		   else
		   {
                min = INF;
                for ( i = 0; i < n; i++ )
				{
                      for ( j = 0; vx[ i ] && j < n; j++ ){
                            if ( !vy[ j ] ){
                                 if ( ( t = -(lx[ i ] + ly[ j ] - edge[ i ][ j ])) < min ){
                                      min = t;
                                 } 
                            }
                      }
                }  
                for ( i = 0; i < n; i++ )
				{
                    if ( vx[ i ] ){
                         lx[ i ] += min;   
                    }
                    if ( vy[ i ] ){
                         ly[ i ] -= min;   
                    }
				}    
		   }   
     }

     return ;
}

int dfs( int k ){
    int i, t;
    
    for ( i = 0 ; i < n; i++ ){
          if ( !vy[ i ] && map[ k ][ i ] ){
               vy[ i ] = 1;
               t = link[ i ];
               link[ i ] = k;
               if ( t == -1 || dfs( t ) ){
                    return 1;   
               }
               link[ i ] = t;
               if ( t != -1 ){
                    vx[ t ] = 1;   
               }   
          }
    }
    return 0;
}