作者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