推 fenzhang:圖有負權最短路做不到N^2吧 06/11 21:51
→ fenzhang:雖然可以SPFA一次後重新標號之後每次DXX做到O(N^3) 06/11 21:58
→ fenzhang:但好像也沒比匈牙利好寫多少 06/11 21:58
推 rebaudiana:N^3匈牙利比起費用流, 難度差不多 ? 06/11 22:14
剛剛學玩學會用來解決二分圖的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://www.ptt.cc/bbs/Prob_Solve/M.1402477415.A.014.html