algorithm - 网络流 - 模拟水管网络

Question

我正在尝试设计一种算法来模拟具有多个源和特定容量的多个汇的管道网络。

到目前为止，我已经尝试使用经典的 Ford-Fulkerson 算法，但我遇到的问题是，给定下图:

    S
    |
    a
   / \
  B   C

给定源容量为 1 的 S，以及汇容量为 1 的 B 和 C - 流将导致 S - a - B，使 B 饱和到 1 并以流 0 离开 C。

我正在尝试在整个网络中均匀分配流量，以便 B 和 C 都收到 0.5。有什么想法吗？

谢谢!

Answer 1

假设您有 n 个源 s₁, ..., s_n 具有源容量 c_i 和 m 下沉 t₁, ..., t_m 。让 f = sum_i c_i。我们想在网络中找到一个可行流，其中每个源 i 都有一个净流 -c_i 并且每个汇都有一个净流f/m。

我们可以通过引入一个 super 源 S 和一个 super 汇 T 并将每个源 i 连接到 来解决这个问题S 通过容量为 c_i 的边 (s_i, S)。我们通过容量边 f/m 将每个 t_i 连接到 T。然后我们只使用源 S 和汇 T 运行 max-flow。

如果无法将 f/m 流量单位精确地推送到每个接收器，则不清楚您要优化什么，但您可能会发现以下两种方法很有用:

• 选择 e 并通过容量为 f/m + e 的边将汇点连接到 T。使用二进制搜索找到最小的 e 使得总流量为 f。这最大限度地减少了 max_i 流入(t_i)
• 选择 e 并通过具有下界 e 的边将汇添加到 T。使用二进制搜索找到仍然允许可行流的最大 e。这使 min_i 流入量 (t_i) 最大化。具有下界的可行流问题可以简化为最大流:http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf在这种情况下，构造非常简单:只需添加一个额外的 super 源 S' 并通过容量 m * e 的边将 S' 连接到 S。通过容量 e 的边将所有接收器连接到 T。检查S'和T之间的最大流量是否为m * e