algorithm - Max Flow 线性时间算法，找到有效流

Question

所以让我解释一下这个问题：

给你一张图表。你找到最大流量。但事实证明，边 e_i 的容量错误。它少了一个。不幸的是，流量在旧容量下已达到极限。

一旦您被告知 e_i 容量错误，请在线性时间内计算新的最大流量（根据边和顶点的数量）。

这是我的计划：（1）你不能只在边上将边 e_i 处的流减少一个，因为你必须违反某些约束：就像流在边上是守恒的。修复流程，以便您可以获得有效的流程。但是怎么做？

（2）有人给我提示：显示有效流=先前流-1.mmm会有所帮助...

帮助。

Answer 1

这里有几个提示：

1. 假设您找到了一条具有非零流的路径（即>= 1），并且包含这条边 e_i。您如何使用此路径使整个流程再次有效？现在，假设你没有得到这条路径。你自己怎么可能得到它？
2. 现在，您知道新图的最大流量要么相同，要么比以前少一个（为什么？）。你怎么能在线性时间内找出哪个？