algorithm - 网络流中的 'increasing Edge'

Question

We are given a network flow, as well as a max flow in the network. An edge would be called increasing edge if increasing its capacity in an arbitrary positive number, would also increase the max flow.

Present an algorithm the finds an increaing edge (if one exists) and runs at $O(n^2)$.

我想到了以下想法-

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

是否正确，我是否符合要求的运行时间？

谢谢!

Answer 1

我认为您只需要找到一条从源到汇的路径，如果最多增加一个节点的容量，该路径将是一条增广路径。

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

然后通过容量最大的边找到与这些顶点相邻的所有其他顶点。

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

总复杂度为 O(N)，所以问您这个问题的人可能还有其他想法。