※ 引述《hil.bbs@ptt2.cc (隨機客)》之銘言：
: ※ 引述《Freak1033 (I ain't gonna be ever17)》之銘言：
: : 理論上這樣可行是沒錯, 不過實作起來真的很難... ^^a
: : 我在比賽中還從來沒有實作成功過 min-cost max-flow...
: : 每次寫一寫就會覺得想法好像有錯, 然後就想不起來自己到底在寫什麼了. XD
: : 徵求容易實作的 min-cost max-flow 演算法. :p
: 問個外行的問題, min-cost max-flow可以用線性規劃來解嗎?
來個外行的回答 @@
可以用線性規劃的方式來解
由於每個不等式係數部份只會出現0,1,-1這幾個值,可以保證求出來的解是整數解
為Integer Programming的Special Case
http://www.daimi.au.dk/dOpt/ilp3.pdf
--
希望沒錯 @@
不過沒人會開法拉利送豆腐的, 大材小用
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.220.139
※ 編輯: windows2k 來自: 140.115.220.139 (09/08 16:11)