作者DJWS (...)
看板ACMCLUB
标题Re: [问题] min-cost max-flow
时间Thu Sep 8 16:36:10 2005
※ 引述《windows2k (KERORO军曹)》之铭言：
: ※ 引述《DJWS (...)》之铭言：
: : 前几天找到了 min-cost max-flow 简介
: : 他提到只要将 max-flow 找出来, 然後不断的找 negative cost cycle
: : 就可以将 min-cost flow 做出来了
: : 然而 negative cost cycle 要怎麽找呢?
: 将cost当做边,当成一个graph
: 跑bellman ford algorithm就能找出graph中是否有negative cost cycle
我知道 Bellman-Ford algo 可以判断图中是否有 negative cycle
但是要怎麽找出组成那个 cycle 的 edge 们呢?
此外 文件上说找 negative cost cycle 找负越多的越好 能有效缩短时间
要怎麽才能找出负最多的 negative cost cycle 呢?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.167.1.212