最大流算法的修改

Question

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

是否有人可以帮助我,我该怎么做呢？

Answer 1

让s是你的源点,并t1和t2两个水槽.

您可以使用以下算法:

1. 使用带有两个水槽的常规最大流量,例如通过无限容量的边缘连接t1和t2超级水槽.您现在拥有最大的解决方案excess(t1) + excess(t2),但它可能是不平衡的.

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

3. 运行另一轮最大流与源t1和宿t2步骤1的残余网络中限制流量从传出t1到c = floor((excess(t1) - excess(t2)) / 2)通过引入超源,例如S连接到t1经由与所述给定容量的边缘c.现在,excess(t2)是您可以发送到两个接收器的最大流量.

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

复杂性是max-flow算法的复杂性.

如果你已经知道如何解决最大流与下限的容量,也可以二进制搜索解决方案,从而在复杂O(log W * f)哪里W是解决方案的价值和f是最大流动的复杂性.