algorithm - 从流中去除边缘后，使用 Ford Fulkerson 有效计算最大流

Question

假设 G 的最大流量已使用 Ford-Fulkerson 计算，但现在从 E 中删除了一条边。如何有效地更新最大流量。

Answer 1

如果e您删除的边穿过切口，则最大流量等于|f| − c(e)，其中|f|是先前计算的最大流量，c(e)是已删除边的容量。

你可以在这里找到详细的解释。