max-flow - 如果每个边缘容量增​​加，最大流量的变化

Question

我需要找到一个线性算法（O（|V| + |E|），它可以在原始最大流量已知但每条边的容量增加 1 的图上找到最大流量。

Answer 1

如果你知道 mincut 是什么，我想你可以为每个切割边缘添加一个到最大流量。