對最大流算法的修改

我試圖解決有關maximum-flow problem的問題。我有一個源和兩個接收器。我需要在這個網絡中找到最大流量。這部分是通用最大流量。但是，這兩個目標都必須在最大流量問題的特殊版本中獲得相同數量的流量。對最大流算法的修改

有沒有人可以幫助我該怎麼做？

2014-01-21 TheGost

-1是什麼原因？ – TheGost

你在說流體分析或計算機網絡信息嗎？ –

我會沿着與你一般最大流量相同的方式開始，除了在每一步，找到兩個增加路徑，一個從源到每個目標。然後向兩條路徑添加足夠的流量，以使兩個目標仍然獲得相同的流量（這通過非邊緣不相交圖形變得複雜一些）。我不確定這樣做是否會實現兩個目標的最大可能性。 – gms7777

讓s成爲您的源頂點，t1和t2這兩個接收器。由通過與無限容量的邊緣連接t1和t2到超匯

使用常規最大流和兩個洗手池，例如：

您可以使用下面的算法。您現在擁有的解決方案的最大數量爲excess(t1) + excess(t2)，但可能不平衡。
如果excess(t1) == excess(t2)，你就完成了。否則，w.l.o.g.讓excess(t1) > excess(t2)
運行另一輪最大流與源t1和步驟1的殘餘網絡中下沉t2通過引入通過連接到t1超源S限制從t1傳出流向c = floor((excess(t1) - excess(t2))/2)，例如具有給定容量的邊緣c。現在，excess(t2)是您可以發送到兩個接收器的最大流量。
如果您需要重建每條邊的流量值，請執行另一輪最大流量以將剩餘流量單位傳輸回源。

複雜性是你最大流算法的複雜性。

如果你已經知道如何解決最大流與下限的容量，也可以二進制搜索解決方案，從而在複雜O(log W * f)其中W是解決方案的價值和f是最大流動的複雜性。

2014-01-22 00:17:41

對不起，它不清楚如何增加一個超級源到t1將流量單位轉移到t2。據我所知，t1仍然是一個匯，流量從't1'到任何其他節點的轉移將是不可能的。對不起，如果我誤解了。 –

@AbhishekBansal將t1視爲正常節點，將t2視爲sink並繼續執行max-flow從新源到t2 –

作者：您能否更明確地解釋步驟4？ –

回答