計算最小的 - 切向加權圖使用

我一直在使用福特Fulkerson算法計算出的最大流量maxflow算法，現在我要實現項目的選擇問題了，我需要計算最大。沒有。可行的項目。我需要找到一個min.cut不包含。具有最大利潤的可行項目。什麼應該是算法找到最小。在知道圖中的最大流量之後切割*我如何使用最大流量來確定包含否的切割。的節點有助於實現最大流量。我需要選擇最佳的節點集合，以使收入最大化。在我的應用程序中，每個節點都與收入相關聯，它也可以是正數也可以是負數。並且還有優先約束條件，例如，如果選擇a，則必須選擇c。是否有人可以告訴我如何實現？計算最小的 - 切向加權圖使用

我在最大流量圖形如下變換它：如果收入（節點）> 0，從源 - >節點添加的邊緣添加其他從節點 - 的邊緣>水槽和我已創建的無限一個EGDE爲優先約束容量

來源

2012-07-06 shalini

不想發現在最終的剩餘圖形飽和邊緣是的意思，但你讀過維基百科上指出HTTP：//en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Project_selection_problem 很明顯，你可以檢查在Cormen的書，但維基簡潔明瞭。 – matcheek 2012-07-06 17:04:14

是的，我已經從cormen自己讀它，我知道，最大流量=切min.capacity，但我的應用程序需要獲得該切我的意思是，我需要知道所有max.profit項目 – shalini 2012-07-07 03:29:00

有優先約束在項目xomewhat像露天採礦問題 – shalini 2012-07-07 17:51:58

我們可以計算min.cut（A，B）通過運行從源頂點DFS/BFS，然後ieafter沒有增廣路

來源

2012-07-11 18:18:44 shalini

福特富爾克森有點在於它可以實現幾種不同的方式的元的算法（埃德蒙斯-卡普是用於FF算法的實例化）。如果您不知道您採用了哪種方式或您擁有哪些信息，您的問題很難回答。

理想情況下，你正在使用某種形式的剩餘圖做算法中的某些類型的廣度優先搜索。當你這樣做時，當你的BFS找不到接收器時，算法應該停止。一旦發生這種情況，第一套剪輯就是您能夠在BFS中找到的所有節點，另一套是您無法找到的所有節點。

如果您正在使用該算法的標籤版本，形成剪切集合是標記集和未標記集。

我希望這會有所幫助。無可否認，你的問題有點難以解析。如果你在這裏找不到足夠的幫助，我會和matcheek有相同的建議（如果你有這本書可以看看維基百科或CLRS）。

來源

2012-07-06 18:14:52

是的，我實現FF算法使用BFS，所以你的意思是，當我沒有更多的擴充路徑，我在不同的擴充路徑遍歷我從bfs找到的所有頂點在我的最低限度削減 – shalini 2012-07-07 03:25:04

繼續：這將是我的答案，包含max.profit – shalini 2012-07-07 03:31:42

的項目，請你想澄清 – shalini 2012-07-07 03:37:49

計算最小的 - 切向加權圖使用

回答

相關問題