POJ 2195 Going Home（KM）- from lanshui_Yang - c++编程基础

题目大意：一张图中，有相等数量的“m” 和 “H” ，分别代表人和房子，要求通过移动人使最终每个房子里都有一个人，输出最小的移动步数。

解题思路：这题是求最小权值匹配，可用KM算法求解，需要注意的是，KM算法求的是最大权值匹配，这里需要把每条边的权值取反，得到最大权值匹配后，再把答案取反。

请看代码：

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#define mem(a,b) memset(a,b,sizeof(a))  
#define INF 0x7fffffff  
using namespace std ;  
const int MAXN = 300 ;  
struct Node  
{  
    int x ;  
    int y ;  
} H[MAXN] , M[MAXN] ;  
int Lx[MAXN] , Ly[MAXN] ;  
bool visx[MAXN] , visy[MAXN] ;  
int yy[MAXN] ;  
int slack[MAXN] ;  
int w[MAXN][MAXN] ;  
char s[MAXN][MAXN] ;  
int n , m ;  
int mcnt , hcnt ;  
int ans ;  
void chu()  
{  
    mem(visx , 0) ;  
    mem(visy , 0) ;  
    mem(yy , -1) ;  
    mcnt = hcnt = 0 ;  
}  
void init()  
{  
    int i , j ;  
    for(i = 0 ; i < n ; i ++)  
    {  
        scanf("%s" , s[i]) ;  
        for(j = 0 ; j < m ; j ++)  
        {  
            if(s[i][j] == 'm')  
            {  
                M[mcnt].x = i ;  
                M[mcnt ++].y = j ;  
            }  
            else if(s[i][j] == 'H')  
            {  
                H[hcnt].x = i ;  
                H[hcnt ++].y = j ;  
            }  
        }  
    }  
}  
int dis(Node a , Node b)  
{  
    return abs(a.x - b.x) + abs(a.y - b.y) ;  
}  
void buildG()  
{  
    int i , j ;  
    for(i = 0 ; i < mcnt ; i ++)  
    {  
        for(j = 0 ; j < hcnt ; j ++)  
        {  
            w[i][j] = -1 * dis(M[i] , H[j]) ;  
        }  
    }  
}  
int dfs(int u)  
{  
    visx[u] = 1 ;  
    int v ;  
    for(v = 0 ; v < hcnt ; v ++)  
    {  
        if(visy[v]) continue ;  
        int t = Lx[u] + Ly[v] - w[u][v] ;  
        if(t == 0)  
        {  
            visy[v] = 1 ;  
            if(yy[v] == -1 || dfs(yy[v]))  
            {  
                yy[v] = u ;  
                return 1 ;  
            }  
        }  
        else  
        {  
            if(slack[v] >




 t)  
                slack[v] = t ;  
        }  
    }  
    return 0 ;  
}  
int KM()  
{  
    int i ;  
    int MAX ;  
    for(i = 0 ; i < mcnt ; i ++)  
    {  
        MAX = -1 * INF ;  
        for(int j = 0 ; j < hcnt ; j ++)  
        {  
            if(MAX < w[i][j])  
                MAX = w[i][j] ;  
        }  
        Lx[i] = MAX ;  
    }  
    mem(Ly , 0) ;  
    for(i = 0 ; i < mcnt ; i ++)  
    {  
        for(int j = 0 ; j < hcnt ; j ++)  
        {  
            slack[j] = INF ;  
        }  
        while (1)  
        {  
            mem(visx , 0) ;  // 每次dfs前都要初始化 ！！  
            mem(visy , 0) ;  
            if(dfs(i))  
                break ;  
            int d = INF ;  
            int k ;  
            for(k = 0 ; k < hcnt ; k ++)  
            {  
                if(!visy[k] && d > slack[k])  
                {  
                    d = slack[k] ;  
                }  
            }  
            for(k = 0 ; k < hcnt ; k ++)  
            {  
                if(visx[k])  
                {  
                    Lx[k] -= d ;  
                }  
                if(visy[k])  
                {  
                    Ly[k] += d ;  
                }  
                if(!visy[k])  
                {  
                    slack[k] -= d ;  
                }  
            }  
        }  
    }  
    ans = 0 ;  
    for(i = 0 ; i < mcnt ; i ++)  
    {  
        ans += w[ yy[i] ][i] ;  
    }  
}  
void solve()  
{  
    buildG() ;  
    KM() ;  
    printf("%d\n" , ans * (-1)) ;  
}  
int main()  
{  
    while (scanf("%d%d" , &n , &m) != EOF)  
    {  
        if(n == 0 && m == 0)  
            break ;  
        chu() ;  
        init() ;  
        solve() ;  
    }  
    return 0 ;  
}