本文主要是介绍HDUnbsp;2255nbsp;奔小康赚大钱（KM算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2255
好久都没有更新博客了……好惭愧
这题是标准的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;
#include<string.h>
int map [ 310 ][ 310 ], match [ 310 ];
int lx [ 310 ],n , ly [ 310 ], sx [ 310 ], sy [ 310 ];
int Match( int u)
{
}
void KM_match()
{
}
int main()
{