6

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

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

4

1 回答 1

8

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。限制从 流出的流t1c = floor((excess(t1) - excess(t2)) / 2)例如通过引入一个通过具有给定容量的边S连接到的超级源。现在,是您可以发送到两个接收器的最大流量。t1cexcess(t2)

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

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

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

于 2014-01-22T00:17:41.890 回答