algorithm - 网络流更新值

Question

我正在练习我书中的算法问题并遇到了这个问题：

给定一个有 n 个节点和 m 个边的有向网络 G，一个源 s，一个汇 t 和一个从 s 到 t 的最大流 f。假设每条边的容量都是一个正整数，描述一个 O(m + n) 时间的算法，用于在以下两种情况下更新流 f。

(i) 边 e 的容量增加 1。

(ii) 边 e 的容量减少 1。

看起来就像遍历网络流边缘和调整流一样简单，但我认为这并不是那么简单。维基百科只给出 O(n^2 m) 或 O(nm^2) 的算法。任何帮助或想法将不胜感激。

score 1 · Accepted Answer

这里有一个解决方案。

假设 e 是 u 和 v 之间的一条边。

增加容量

增加容量的想法是简单地在残差流图中对从 s 到 t 的路径进行 DFS。

如果边缘在最大流量中没有被取消，那么你就完成了。

否则，我们的想法是查看剩余流图中是否存在从 u 到 v 的替代路径。这需要 O(n+m)。如果找到，则可以将最大流量增加 1。

否则，您需要减少流量。为此，您需要找到一条从 u 到 s 的路径，沿着该路径，流量可以增加 1，以及从 t 到 v 的路径，流量可以沿着该路径增加 1。（增加方向相反，因此这会减少来自s 到 t)。