作者DJWS (...)
看板ACMCLUB
标题Re: [问题] min-cost max-flow
时间Fri Sep 9 14:14:34 2005
※ 引述《[email protected] (I ain't gonna be ever17)》之铭言：
: ※ 引述《[email protected] (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