algorithm - 修改最大流量算法

Question

我试图解决一个关于最大流量问题的问题。我有一个源和两个接收器。我需要在这个网络中找到一个最大流量。这部分是一般的最大流量。但是，在这个特殊版本的最大流量问题中，两个目标都必须获得相同的流量。

有没有人可以帮助我该怎么做？

Answer 1

让s成为您的源顶点和t1两个t2汇点。

您可以使用以下算法：

1. 使用具有两个接收器的常规最大流，例如通过具有无限容量的边连接t1和连接t2到超级接收器。您现在有了 maximum 的解决方案excess(t1) + excess(t2)，但它可能不平衡。

2. 如果excess(t1) == excess(t2)，你就完成了。否则，wlog 让excess(t1) > excess(t2)

3. t1在步骤 1 的残差网络中使用源和接收器运行另一轮最大流t2。限制从 流出的流t1，c = floor((excess(t1) - excess(t2)) / 2)例如通过引入一个通过具有给定容量的边S连接到的超级源。现在，是您可以发送到两个接收器的最大流量。t1cexcess(t2)

4. 如果您需要重建每条边的流量值，请执行另一轮最大流量以将excess(t1) - excess(t2)剩余的流量单位传输回源。

复杂性是您的最大流量算法的复杂性。

如果您已经知道如何用下限容量求解最大流，您还可以对解进行二分搜索，从而得到解值在O(log W * f)哪里的复杂度，最大流复杂度在哪里。Wf