作者wasaiwang (王先生...)
看板Prob_Solve
标题[请益] min-cost max-flow problem
时间Thu Mar 20 13:40:17 2008
在 max-flow network problem 中,
假设需要达到一个 flow F,
但目前所得到的 max-flow f < F.
则可以在得出 max-flow = f 的 graph G 上,
直接增加 edge 上的 capacity後,
再继续寻找 augmenting path,
进而得到更大的 max-flow,
直到所得到的 max-flow f = F.
若现在是在 min-cost max-flow problem,
是否也可以像上述部分一样,
当所得出的 max-flow f < 目标 flow F,
直接在原来的 graph 上增加 edge 的 capacity 後,
继续寻找 augmenting path,
而不需要在增加 edge 上的 capacity 後,
无视原本得到的 max-flow f,
重新计算一次新的 max-flow ?
第一次发问, 不知是否有表达清楚, 希望大家可以一起讨论. Thanks.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.75.92
1F：→ a127a127:这样可能会出现负圈吧? 03/21 00:18