看板ACMCLUB
标 题Re: [问题] min-cost max-flow
发信站批踢踢兔 (Thu Sep 8 14:41:43 2005)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ 引述《[email protected] (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
理论上这样可行是没错, 不过实作起来真的很难... ^^a
我在比赛中还从来没有实作成功过 min-cost max-flow...
每次写一写就会觉得想法好像有错, 然後就想不起来自己到底在写什麽了. XD
徵求容易实作的 min-cost max-flow 演算法. :p
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 140.109.224.64