Note: This article is available in Chinese only. 本文暂无英文版本。
View original
学完了km..感觉匈牙利真是非常的。。easy… 匈牙利算法学习链接
有一种题目会用1*2的小格子填充大的，问能不能填满之类的，可以用匈牙利搞。hdu 4185解题报告 poj2446解题报告
其实主要是关于建图的启示，上面两个题，还有这道题： poj1325解题报告
还有就是一些有用的结论：
**(1)二分图的最小顶点覆盖 **
最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。
Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。
(2)DAG图的最小路径覆盖
用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。
结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）
(3)二分图的最大独立集
最大独立集问题： 在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值
结论：二分图的最大独立集数 = 节点数（n）— 最大匹配数（m）
还有一个比较常用的角度：n个数的某种排列，可以看做是一个位置集合{1..n}和数字集合{1..n}的二分图最大匹配。可以用来剪枝什么的。hdu3225解题报告