[請益] ZeroJudge大專部 d072

[bleed1979 (十三)]

題目網址：
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
推 DJWS:optimal assignment有O(V^3)及O(VElogV)的演算法
推 DJWS:提示裡面說匈牙利演算法是O(V^2)，可能最近有發明新算法吧？
→ bleed1979:我想到了用背包來解決內文描述的問題，先試試看
推 DJWS:用背包要怎麼解呢?
→ bleed1979:看來是失敗了，本想說把行列所包含的0當成重量
→ bleed1979:每行每列是等價的，但我忽略了行列有重疊的0，重量不準
→ bleed1979:我把問題詳述在C版，希望高人氣能有解
推 yoco315:奇怪,今天想再去看題目,發現這一題無法檢視了..
推 DJWS:http://140.122.185.166/ZeroJudge/ShowThread?postid=40
→ yoco315:怪不得拿掉了...