Re: Judge 事務雜記
※ 引述《windows2k (代替孟子來懲罰你)》之銘言：
: ※ 引述《DJWS (...)》之銘言：
: : 這篇我找到了 ^^
: : 看完之後, 發現這方法, 跟我之前貼上來的程式碼
: : 扯不上任何關係吧
: : 還是說
: : 我上次貼的程式碼, 只是匈牙利演算法的其中一種特例呢??
: 匈牙利演算法是拿來找Maximum matching, 非 Maximum weighted matching
: 要解Maximum weighted matching時,依照每次所給的資訊,動態重新建構一張graph
: 作Maximum Matching,如果找到Perfect Matching即為最佳解
: 建圖的方法,就如OFO裡講的那樣
動態的重新建構一張graph ... 至以下
這個過程，也叫做匈牙利演算法喔!!
只是 DJWS 找到的匈牙利的 code 是用於 edge cost 都相同的情況。
而 ofo 上的匈牙利是可以用於 edge cost 不相同的情況。這樣的方法
也的的確確叫做"hungarian method" (可以稍微利用一下google)
當然edge cost 都相同的情況下，可以有比較便捷的方式。
不過我比較好奇的。
匈牙利演算法中有一步是這樣的"在矩陣之中用最少的線段把所有的0 都覆蓋住"
這邊大家是怎麼去實作的呢? (我一直覺得我的這一部份實作並不好)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.168.132.119
討論串 (同標題文章)