[請益] min-cost max-flow problem
看板Prob_Solve (計算數學 Problem Solving)作者wasaiwang (王先生...)時間16年前 (2008/03/20 13:40)推噓0(0推 0噓 1→)留言1則, 1人參與討論串1/1
在 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
→
03/21 00:18, , 1F
03/21 00:18, 1F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
