现在的位置: 首页 > 综合 > 正文

POJ二分匹配总结_匈牙利算法

2018年02月19日 ⁄ 综合 ⁄ 共 931字 ⁄ 字号 评论关闭

二分匹配模板


poj

1469

1274
2239 Selecting Courses
1422 Air Raid 最小路径覆盖
1325 Machine Schedule
1719 Shooting Contest
2594 Treasure Exploration
2195 Going Home带权二分图(km算法)
2446 Chessboard
1904 King's Quest
3342 Party at Hali-Bula
3216 Repairing Company
POJ3020 - Antenna Placement

POJ 1325 最小点覆盖=最大二分匹配

POJ 1087 floyd闭包传递

POJ 1422 2594 最小路径覆盖=N-最大二分匹配,要确定题意一个点是否可以重复走,如果可以,就要用闭包传递建立二分图。

POJ 1466 最大独立团,最大独立团=顶点数减去匹配的对数,但是这里相同的两个点会匹配成两对,例如 下图

二分图

用匈牙利算法 1配2,然后2又配了1,最大匹配是两对,而实际上1和2是同一队,所以最大独立团=顶点数n-最大匹配/2

当然可以修改匈牙利算法,当1匹配到2的时候同时标记两个点都不能再匹配就行了那样最大独立团就=顶点数-最大匹配(修改的匈牙利算法),这样也快一点,用邻接表存储图会更快,不用为每个点去遍历n个点。

抱歉!评论已关闭.