Изменение максимального потока при увеличении емкости каждого края

Question

Мне нужно найти линейный алгоритм (O (| V | + | E |), который найдет максимальный поток на графике, где известен максимальный поток потока, но емкость каждое ребро увеличивается на 1.

Answer 1

Если вы знаете, что mincut, я полагаю, вы можете просто добавить один к максимальному потоку для каждого срез края.