[請益] min-cost max-flow problem

[wasaiwang (王先生...)]

在 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
→ a127a127:這樣可能會出現負圈吧?