algorithm - 网络流中的“增加边缘”

Question

我们得到一个网络流量，以及网络中的最大流量。如果以任意正数增加其容量，则边缘将被称为增加边缘，也会增加最大流量。

提出一种算法，找到一个增加的边缘（如果存在）并以 $O(n^2)$ 运行。

我想到了以下想法——

• 找到图中的最小割，因为它是用福特-富尔克森算法给我们的。
• 将切口左侧所有边的容量增加 1。
• 在残差网络中运行 BFS 以查找是否存在改进的路径。如果存在，我们将拥有越来越大的优势。要找到它，我们必须将原始网络与新网络进行比较。我们必须这样做 n 次，因为每次我们将容量增加 1 时都必须检查改进的路径。

是否正确，我是否符合所需的运行时间？

谢谢！

Answer 1

我认为你只需要找到一条从源到接收器的路径，如果最多增加一个节点的容量，这将是一条增广路径。

首先找到剩余容量可以到达的所有顶点的最佳路径。如果你找到了水槽，那么你一开始就没有得到最大流量。

然后找到与这些顶点相邻的所有其他顶点，尽管边具有容量。

然后尝试找到从这些顶点到汇的增广路径。

总复杂度是 O(N)，所以问你这个问题的人可能有别的想法。