Question

求一般图的最大权匹配的算法（最好详细一些，注意数最大权匹配），高分求助！

或者解决一个问题，给2N个点，两两之间有一条带权边（即构成完全图），找到N条两两间没有公共端点的N条边将所有点覆盖，使边权之和最小。直接拆成左半部2N个点，右半部2N个点，然后再用KM求是错误的。一般图的最大权匹配肯定可以解决，但如果有其他方法也行。动态规划除外。

一楼不要乱复制粘贴行吗？这和MST差了十万八千里。。谁不知道kruskal和prim啊。这个和最小生成树最少差了两个层次，果断不给分。

Answer 1

Algorithmus 3.3 Kruskal's Algorithm 时间复杂度 O(mlog n)
m边数 n点数
输入: 图 G = (V;E) 和 权c : E -》R.
输出: 一棵最优树 T.
begin
把所有边以权的大小按从小到大排序
T := (VG，ET ) := (VG， 空);
for i = 1 to m do
if T + ei 没有圈 then
T := (VG;ET 并上 {ei});
if end
for end
end

或者 Algorithmus 3.5 Prim's Algorithm 时间复杂度O(m+n log n)

Answer 2

KM不行吗？我觉得KM可以，因为你那个是完全图来的，如果不行那只能最小费用最大流咯 ！时间复杂度相对高一些