匈牙利算法总结

学完了km..感觉匈牙利真是非常的。。easy…
匈牙利算法学习链接

 

有一种题目会用1*2的小格子填充大的,问能不能填满之类的,可以用匈牙利搞。hdu 4185解题报告 poj2446解题报告

其实主要是关于建图的启示,上面两个题,还有这道题: poj1325解题报告

还有就是一些有用的结论:

(1)二分图的最小顶点覆盖 

最小顶点覆盖要求用最少的点(X或Y中都行),让每条边都至少和其中一个点关联。

Knoig定理:二分图的最小顶点覆盖数等于二分图的最大匹配数。

(2)DAG图的最小路径覆盖

用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点,这就是DAG图的最小路径覆盖问题。

结论:DAG图的最小路径覆盖数 = 节点数(n)- 最大匹配数(m)

(3)二分图的最大独立集

最大独立集问题: 在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值

结论:二分图的最大独立集数 = 节点数(n)— 最大匹配数(m)

还有一个比较常用的角度:n个数的某种排列,可以看做是一个位置集合{1..n}和数字集合{1..n}的二分图最大匹配。可以用来剪枝什么的。hdu3225解题报告

 

选区_079 选区_078

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz