最大流算法的修改

Question

我尝试解决关于最大流问题的一个问题。我有一个源点和两个汇点。我需要在这个网络中找到最大的流量。这部分是通用的最大流问题。然而，在特殊版本的最大流问题中，这两个目标必须获得相同数量的流量。

有没有人能帮我应该怎么做呢？

- TheGost

---

-1的原因是什么？ - TheGost

你是在谈论流体分析还是计算机网络消息？ - Thomas Matthews

我会从类似于一般最大流的方式开始，除了每一步都要找到两条增广路径，一条从源点到每个目标点。然后添加足够的流量到这两条路径上，以便两个目标点仍然获得相同数量的流量（非边不相交的图有些复杂）。我不确定这样做是否会实际上达到两个目标点的最大可能流量。 - gms7777

“不清楚”的问题是如何定义的？在我看来，被问到的内容非常明显。实际上，这是一个有趣的问题。 - Niklas B.

Answer 1

让s成为源点，t1和t2成为两个汇点。您可以使用以下算法：

1. 使用常规的双汇最大流算法，在网络中连接一个带有无限容量边的超级汇点t1和t2。现在你已经得到了具有最大excess(t1) + excess(t2)的解，但它可能不平衡。
2. 如果excess(t1) == excess(t2)，则完成。否则，不失一般性地假设excess(t1) > excess(t2)
3. 在第1步的剩余网络中以源点t1和汇点t2运行另一轮最大流算法。限制从t1出发的流量为c = floor((excess(t1) - excess(t2)) / 2)，例如通过引入一个超级源点S连接到带有给定容量c的t1。现在，excess(t2)即为您可以发送到两个汇点的最大流。
4. 如果需要重建每条边的流值，请进行另一轮最大流运输excess(t1) - excess(t2)剩余单位的流返回到源点。

算法复杂度取决于您使用的最大流算法。

如果您已经知道如何使用下界容量解决最大流问题，也可以二分搜索解决方案，其复杂度为O(log W * f)，其中W是解决方案值，f是最大流复杂度。

- Niklas B.

---

很抱歉，我不清楚将超级源添加到t1中如何将流量单位传输到t2。据我所知，t1仍将保持为汇点，并且从t1到任何其他节点的流量转移将是不可能的。如果我有误解，请再次原谅。 - Abhishek Bansal

@AbhishekBansal 将t1视为普通节点，将t2视为汇点，并从新源到t2进行最大流处理。 - Kudayar Pirimbaev

给作者：您能更明确地解释第四步吗？ - Kudayar Pirimbaev

@KudayarPirimbaev t1所有的边都是入边（因为它是一个汇点）。它怎么能被认为是一个正常的节点呢？ - Abhishek Bansal

@AbhishekBansal 我认为假设图是双向的，在你的情况下，我猜你需要反转所有边缘到t1的方向，除了来自新源的那个，试试看，我不确定。 - Kudayar Pirimbaev