我试图解决一个关于最大流量问题 http://en.wikipedia.org/wiki/Maximum_flow_problem。我有一个源和两个接收器。我需要找到该网络中的最大流量。这部分是一般的最大流量。然而，在这个特殊版本的最大流量问题中，两个目标必须获得相同的流量。
有谁可以帮助我我该怎么做才能做到这一点？
Let s是你的源顶点并且t1 and t2两个水槽。
您可以使用以下算法：
使用带有两个接收器的常规最大流量，例如通过连接t1 and t2通过具有无限容量的边缘到超级水槽。现在你已经有了最大的解决方案excess(t1) + excess(t2)，但可能会不平衡。
If excess(t1) == excess(t2)，你就完成了。否则，w.l.o.g.让excess(t1) > excess(t2)
使用源运行另一轮最大流t1和下沉t2在步骤1的剩余网络中，限制从t1 to c = floor((excess(t1) - excess(t2)) / 2)，例如通过引入超级源S连接到t1通过给定容量的边c. Now, excess(t2)是您可以发送到两个接收器的最大流量。
如果需要重建每条边的流量值，请进行另一轮最大流量来传输excess(t1) - excess(t2)剩余单位流量返回源头。
复杂性在于最大流算法的复杂性。
如果您已经知道如何解决具有下限容量的最大流，您还可以对解决方案进行二分搜索，从而导致复杂性O(log W * f) where W是解值并且f是最大流复杂度。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
