作者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