在 Ford Fulkerson 算法中添加新边后有效计算最大流量？

Question

假设已经使用 Ford-Fulkerson 计算了 G 的最大流量，并向 E 添加了一条具有单位容量的新边。如何有效地更新最大流量。 （t不是必须更新的流的值，而是流本身。

Answer 1

设 G' 为新边 e 添加到 G 的图。请注意，我们保留了剩余边缘的容量和流量。

现在在G'中找到增广路径p。

如果 p 存在，则将 G' 中沿该路径的流量更新为 1。否则，流量保持不变。

这给出了最终的流量值。这是正确的，因为如果 p 存在，那么它会通过 e。因此，沿 p 的流量更新恰好为 1。由于 Folk-Fulkerson 算法以积分步骤增加流量，因此 G'[=32 中没有增广路径=] 更新后。

如果 p 不存在，则根据 mincut-maxflow 参数，这是最大流，因为最小切割为 0。