Максимальный поток Линейный алгоритм времени, Найти правильный поток

Question

Итак, позвольте мне объяснить вопрос:

Вам дан график. Вы найдете максимальный поток. Но оказывается, что у края, e_i, была неправильная способность. Это был один меньше. К сожалению, поток был максимизирован на старой мощности.

Вычислите новый максимальный поток за линейное время (с точки зрения количества ребер и вершин), как только вам скажут, что e_i имеет неправильную емкость.

Вот мой план: (1) Вы не можете сбросить поток на ребре e_i по одному на ребре, потому что вы должны нарушать определенные ограничения: как поток сохраняется на ребре. Исправьте потоки, чтобы вы могли получить действительный поток. Но как?

(2) Кто-то дал мне подсказку: будет полезно показать действительный поток = предыдущий поток -1.ммм...

Помогите.

Answer 1

Вот пара советов:

1. Предположим, вы нашли путь с ненулевым потоком (т.е. >= 1), и содержал этот край e_i. Как вы можете использовать этот путь, чтобы снова сделать общий поток действительным? Теперь предположим, что вам не дан этот путь. Как ты мог получить это сам?
2. Теперь вы знаете, что максимальный поток нового графа либо такой же, либо на один меньше, чем раньше (почему?). Как вы можете узнать, что за линейное время?