作者windows2k (KERORO军曹)
看板ACMCLUB
标题Re: [问题] min-cost max-flow
时间Thu Sep 8 16:10:10 2005
※ 引述《[email protected] (随机客)》之铭言：
: ※ 引述《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)