[问题] 匈牙利算法的复杂度 sandy4444 PTT批踢踢实业坊

[问题] 匈牙利算法的复杂度

楼主: sandy4444 (质朴) 2014-06-11 17:03:33

刚刚学玩学会用来解决二分图的max cost perfect matching
的匈牙利算法
复杂度有 O(n^4) 和 O(n^3)(比较难用)
使用过程很漂亮
但是跟其他求 max cost perfect matching 在复杂度和效率比较
是否弱很多
把二分图转换成 s-t flow
用每次找最短 augment path 的方法算出来的在速度上还弱(O(n^3))
所以想问的是在慢一个维度下
为什么大家这么爱匈牙利算法???

作者: fenzhang (分帐) 2014-06-11 21:51:00

图有负权最短路做不到N^2吧虽然可以SPFA一次后重新标号之后每次DXX做到O(N^3)但好像也没比匈牙利好写多少

作者: rebaudiana (微甜) 2014-06-11 22:14:00

N^3匈牙利比起费用流, 难度差不多 ?

继续阅读

[问题] 分开、组合huadi73 [问题] 无法判定程式终结dharma [问题] ICPC 6036 Stacking Platesmob5566 [问题] 问题的分类dharma Re: [问题] 验证某数是否为质数是NP问题DJWS Re: [问题] 验证某数是否为质数是NP问题dharma Re: [问题] 验证某数是否为质数是NP问题johnathan717 [问题] 验证某数是否为质数是NP问题dharma [问题] 如何以数学公式及算法表达程式tree581 [解题]排列组合CFengY