※ 引述《Freak1033.bbs@ptt2.cc (I ain't gonna be ever17)》之銘言：
: ※ 引述《windows2k.bbs@ptt.cc (KERORO軍曹)》之銘言：
: : 將cost當做邊,當成一個graph
: : 跑bellman ford algorithm就能找出graph中是否有negative cost cycle
: 理論上這樣可行是沒錯, 不過實作起來真的很難... ^^a
: 我在比賽中還從來沒有實作成功過 min-cost max-flow...
: 每次寫一寫就會覺得想法好像有錯, 然後就想不起來自己到底在寫什麼了. XD
: 徵求容易實作的 min-cost max-flow 演算法. :p
如果有的話..我也想知道 :p
最好還有程式碼~~~
btw
判斷一個圖有沒有 negative cost cycle
用 Bellman-Ford algo 或 Floyd-Warshall algo 都可以做
所以要找出任意一個 negative cost cycle
應該也是 P-time 的問題吧... (不負責任推測)
如果要找出負的最多的 negative cost cycle
恩...這是 NP-Complete problem 嗎? 我也不知道 :p
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.15.152