二分图最佳匹配

如果G为加权二分图,则权值和最大的完备匹配称为最佳匹配.

求一个二分图的最佳匹配的普遍算法是KM(Kuhn-Munkres)算法.

KM算法的基本思想是,把权值转化为可行顶标,再用匈牙利算法求出一组完备匹配,如果无法求出完备匹配,则修改可行顶标,直至找到完备匹配为止,这时的完备匹配为最佳匹配.

Kuhn－Munkras算法流程：

(1)初始化可行顶标的值

(2)用匈牙利算法寻找完备匹配

(3)若未找到完备匹配则修改可行顶标的值

(4)重复(2)(3)直到找到相等子图的完备匹配为止

• ·希朗拉
• ·物自身
• ·蠢才秀Jackass
• ·为我之物
• ·魔洞战记
• ·鄂侯
• ·九侯
• ·合金装备掌上行动
• ·大庆石油大学
• ·马克·华菲