多商品流动

Question

为了备考，我刚刚从DPV教材上写了几章问题。其中之一，我遇到了一些麻烦，但我已经取得了一些进展：

​

​

我的解决方案：

我将使用线性规划来最大化x，其中SUM {flow_i(s_i，v)对于所有i，其中v是连接到源s_i} >= x* d_i的节点。

受制于这些限制

• 对于每个边e，f1+..fk <= c_e
• 对于每个边e，flow_e >= 0
• 还有一些我不确定的约束

我想我是在正确的轨道上，但我需要一些帮助，以进一步。我应该考虑使用一个超级节点来将这个问题减少到一个常规的最大流问题吗？

任何帮助都会很好！谢谢。

Answer 1

是的，解决多源、多汇商品流问题的一个典型方法是引入超级源和超级汇。然后将所有源s1...sk连接到超级源。将每个接收器t1、...tk连接到超级接收器.

重要：为所有离开或进入任何超级节点的边缘提供一个非常大的容量。

目标：最大限度地提高总通透性。(流出源的所有边的流量之和1.k)

制约因素：

边缘容量限制：

你已经说对了。

• 对于每个边e，f1+..fk <= c_e

*流量保护(Flow-in == Flow_out):*

• 对于每个顶点v，流到v的和=离开v的和。

需求满足：

• 对于每个汇t_i，流到t_i (以t_i结尾的所有边)和>= demand_i

非零流，你已经有了。

下面是一份无障碍讲义，它引用了您的具体问题。具体来说，看看讲义中的示例2。