PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[請益] ZeroJudge大專部 d072

看板Prob_Solve (計算數學 Problem Solving)作者 (十三)時間15年前 (2009/12/13 23:54), 編輯推噓5(5推 0噓 5→)
留言10則, 3人參與, 最新討論串1/1
題目網址： 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
推
12/14 08:54, , 1F
optimal assignment有O(V^3)及O(VElogV)的演算法
12/14 08:54, 1F
推
12/14 08:59, , 2F
提示裡面說匈牙利演算法是O(V^2)，可能最近有發明新算法吧？
12/14 08:59, 2F
→
12/14 10:03, , 3F
我想到了用背包來解決內文描述的問題，先試試看
12/14 10:03, 3F
推
12/14 15:18, , 4F
用背包要怎麼解呢?
12/14 15:18, 4F
→
12/14 16:12, , 5F
看來是失敗了，本想說把行列所包含的0當成重量
12/14 16:12, 5F
→
12/14 16:12, , 6F
每行每列是等價的，但我忽略了行列有重疊的0，重量不準
12/14 16:12, 6F
→
12/14 16:14, , 7F
我把問題詳述在C版，希望高人氣能有解
12/14 16:14, 7F
推
12/18 01:29, , 8F
奇怪,今天想再去看題目,發現這一題無法檢視了..
12/18 01:29, 8F
→
12/18 09:10, , 10F
怪不得拿掉了...
12/18 09:10, 10F
‣ 更多 bleed1979 的文章
文章代碼(AID): #1B9Guglp (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 bleed1979 的文章
文章代碼(AID): #1B9Guglp (Prob_Solve)