题目链接：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();
#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()
{