二分图小总结

知识

二分图大讲堂——彻底搞定最大匹配数(最小覆盖数)、最大独立数、最小路径覆盖、带权最优匹配

这一篇已经足够了。

模板

匈牙利算法,复杂度O(V*E),使用“vector邻接表”存储图。MAXN为单边最大节点数量,需要按照题目要求调整,INF是理论最大值不够的话按照题目要求调整。左手边和右手边的节点序号从0开始,建图前,执行init,并正确配置nx(左手边节点数量)和ny(右手边节点数量),BGM_H()返回最大匹配数。

Hopcroft-Karp算法,复杂度O(sqrt(V) * E),适配方法同匈牙利算法模板,调用是BGM_HK(),不适合活用。

配套练习

二分图・ア

POJ 1274 The Perfect Stall(教学题)
POJ 2446 Chessboard(骨牌模型转化)
POJ 2594 Treasure Exploration(允许相交的最小路径覆盖)
POJ 1325 Machine Schedule(适当建图,最小点覆盖问题)
POJ 1469 COURSES(教学题)
HDU 3225 Flowers Placement(匈牙利算法在DFS中的剪枝作用)

 

Scroll to top