Как генерируется поток для алгоритма Malhotra?

Question

[alex_agaphe]

Есть алгоритм -
https://cp-algorithms.com/graph/mpm.html
Находятся точки с самым высоким потенциалом и пушуются потоки оттуда.
На нулевом этапе потенциал равен минимум входных и выходных сумме капасити.
Мы добавляет этот потенциал к ответу. Что будет, если до этого потока не хватит, чтобы заполнить капасити? Он же уже добавлен в ответ, или я что-то не понимаю?

Answer 1

[0Z0SK0]

поток всегда будет помещаться в ребра, потому что по определению это минимум из двух сумм остаточных пропускных способностей:

Сумма остатков входящих рёбер ≥ минимум
Сумма остатков исходящих рёбер ≥ минимум

и проталкивать он будет до тех пор, пока не протолкнуто ровно минимум единиц потока

Пусть для вершины v:
Входящие ребра: a→v с остатком 2, b→v с остатком 3 (сумма 5)
Исходящие ребра: v→c с остатком 4, v→d с остатком 1 (сумма 5)
p(v) = min⁡(5, 5) = 5

пошагово:
Для подтягивания: берем 2 из a→v и 3 из b→v (суммарно 5).
Для проталкивания: отправляем 4 в v→c и 1 в v→d (суммарно 5).
Общий поток увеличится на 5, ребра без остатка