作者bleed1979 (十三)
站內Prob_Solve
標題[請益] ZeroJudge大專部 d072
時間Sun Dec 13 23:54:13 2009
題目網址：
http://140.122.185.166/ZeroJudge/ShowProblem?problemid=d072
解題演算法：
Hungarian Algorithm
這是屬於Matching的演算法。
我想向有實作過這個演算法的人請益。
想請教在找最少行列數能包含所有0的這一步，
有沒有除了DFS以外更快的作法？
時間限制1s且至少有600*600的陣列，
我將實作出來的程式上傳後TLE。
Overhead不用說一定是我請益的這個點，
希望有更快方法的人能給予指導，感謝。
(如果有需要我再貼我的code，一開始就貼怕有人會踩到地雷)
Bleed
--
World of bleed1979
http://bleed1979.myweb.hinet.net/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97
1F：推 DJWS:optimal assignment有O(V^3)及O(VElogV)的演算法 12/14 08:54
2F：推 DJWS:提示裡面說匈牙利演算法是O(V^2)，可能最近有發明新算法吧？ 12/14 08:59
3F：→ bleed1979:我想到了用背包來解決內文描述的問題，先試試看 12/14 10:03
4F：推 DJWS:用背包要怎麼解呢? 12/14 15:18
5F：→ bleed1979:看來是失敗了，本想說把行列所包含的0當成重量 12/14 16:12
6F：→ bleed1979:每行每列是等價的，但我忽略了行列有重疊的0，重量不準 12/14 16:12
7F：→ bleed1979:我把問題詳述在C版，希望高人氣能有解 12/14 16:14
8F：推 yoco315:奇怪,今天想再去看題目,發現這一題無法檢視了.. 12/18 01:29
10F：→ yoco315:怪不得拿掉了... 12/18 09:10