我试图解决一个关于最大流量问题的问题。我有一个源和两个接收器。我需要在这个网络中找到一个最大流量。这部分是一般的最大流量。但是,在这个特殊版本的最大流量问题中,两个目标都必须获得相同的流量。
有没有人可以帮助我该怎么做?
我试图解决一个关于最大流量问题的问题。我有一个源和两个接收器。我需要在这个网络中找到一个最大流量。这部分是一般的最大流量。但是,在这个特殊版本的最大流量问题中,两个目标都必须获得相同的流量。
有没有人可以帮助我该怎么做?
让s
成为您的源顶点和t1
两个t2
汇点。
您可以使用以下算法:
使用具有两个接收器的常规最大流,例如通过具有无限容量的边连接t1
和连接t2
到超级接收器。您现在有了 maximum 的解决方案excess(t1) + excess(t2)
,但它可能不平衡。
如果excess(t1) == excess(t2)
,你就完成了。否则,wlog 让excess(t1) > excess(t2)
t1
在步骤 1 的残差网络中使用源和接收器运行另一轮最大流t2
。限制从 流出的流t1
,c = floor((excess(t1) - excess(t2)) / 2)
例如通过引入一个通过具有给定容量的边S
连接到的超级源。现在,是您可以发送到两个接收器的最大流量。t1
c
excess(t2)
如果您需要重建每条边的流量值,请执行另一轮最大流量以将excess(t1) - excess(t2)
剩余的流量单位传输回源。
复杂性是您的最大流量算法的复杂性。
如果您已经知道如何用下限容量求解最大流,您还可以对解进行二分搜索,从而得到解值在O(log W * f)
哪里的复杂度,最大流复杂度在哪里。W
f