作者sandy4444 (质朴)
看板Prob_Solve
标题[问题] 匈牙利演算法的复杂度
时间Wed Jun 11 17:03:33 2014
刚刚学玩学会用来解决二分图的max cost perfect matching
的匈牙利演算法
复杂度有 O(n^4) 和 O(n^3)(比较难用)
使用过程很漂亮
但是跟其他求 max cost perfect matching 在复杂度和效率比较
是否弱很多
把二分图转换成 s-t flow
用每次找 最短 augment path 的方法算出来的在速度上还弱(O(n^3))
所以想问的是在慢一个维度下
为什麽大家这麽爱匈牙利演算法???
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 210.69.191.1
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1402477415.A.014.html
1F：推 fenzhang:图有负权最短路做不到N^2吧 06/11 21:51
2F：→ fenzhang:虽然可以SPFA一次後重新标号之後每次DXX做到O(N^3) 06/11 21:58
3F：→ fenzhang:但好像也没比匈牙利好写多少 06/11 21:58
4F：推 rebaudiana:N^3匈牙利比起费用流, 难度差不多 ? 06/11 22:14