这题是标准的KM算法,贴上大神的解释吧…… Kuhn-Munkras算法流程: (1)初始化可行顶标的值 (2)用匈牙利算法寻找完备匹配 (3)若未找到完备匹配..." />
当前位置: 代码迷 >> 综合 >> HDUnbsp;2255nbsp;奔小康赚大钱(KM算法)
  详细解决方案

HDUnbsp;2255nbsp;奔小康赚大钱(KM算法)

热度:8   发布时间:2024-01-04 10:57:00.0

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2255

 

好久都没有更新博客了……好惭愧HDU <wbr>2255 <wbr>奔小康赚大钱(KM算法)

 

这题是标准的KM算法,贴上大神的解释吧……

Kuhn-Munkras算法流程:

(1)初始化可行顶标的值
(2)用匈牙利算法寻找完备匹配
(3)若未找到完备匹配则修改可行顶标的值
(4)重复(2)(3)直到找到相等子图的完备匹配为止 

[KM算法的几种转化]

KM算法是求最大权完备匹配,如果要求最小权完备匹配怎么办?方法很简单,只需将所有的边权值取其相反数,求最大权完备匹配,匹配的值再取相反数即可。

KM算法的运行要求是必须存在一个完备匹配,如果求一个最大权匹配(不一定完备)该如何办?依然很简单,把不存在的边权值赋为0

KM算法求得的最大权匹配是边权值和最大,如果我想要边权之积最大,又怎样转化?还是不难办到,每条边权取自然对数,然后求最大和权匹配,求得的结果a再算出e^a就是最大积匹配。至于精度问题则没有更好的办法了。

看不懂转更详细的解释:http://blog.163.com/huangbingliang@yeah/blog/static/94161399201011291044527/

附上我的代码:

 

C语言: 高亮代码由发芽网提供
#include<stdio.h>
#include<string.h>

int map [ 310 ][ 310 ], match [ 310 ];
int lx [ 310 ],n , ly [ 310 ], sx [ 310 ], sy [ 310 ];

int Match( int u)
{
    int j;
    sx [ u ] = 1;
    for( j = 1; j <=n; j ++)
        if( ! sy [ j ] && map [ u ][ j ] == lx [ u ] + ly [ j ])
        {
            sy [ j ] = 1;
            if( ! match [ j ] || Match( 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 ] = map [ i ][ 1 ];
        for( j = 2; j <=n; j ++)
            lx [ i ] = lx [ i ] > map [ i ][ j ] ? lx [ i ] : map [ 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( Match( i)) break;
            min = 2147483647;
            for( j = 1; j <=n; j ++)
                if( sx [ j ])
                {
                    for( k = 1; k <=n; k ++)
                        if( ! sy [ k ])
                            min = min >( lx [ j ] + ly [ k ] - map [ j ][ k ]) ?( lx [ j ] + ly [ k ] - map [ j ][ k ]) : min;
                }
            for( j = 1; j <=n; j ++) if( sx [ j ]) lx [ j ] -= min;
            for( k = 1; k <=n; k ++) if( sy [ k ]) ly [ k ] += min;
        }
    }
}

int main()
{
    int i , j , num;
    while( scanf( "%d" , &n) != EOF)
    {
        for( i = 1; i <=n; i ++)
            for( j = 1; j <=n; j ++)
                scanf( "%d" , & map [ i ][ j ]);
        KM_match();
        num = 0;
        for( i = 1; i <=n; i ++)
            if( match [ i ]) num += map [ match [ i ]][ i ];
        printf( "%d \n " , num);
    }
    return 0;
}