Изменения
→Асимптотика
'''return''' flow
'''for''' (<tex>u</tex> = ptr[<tex>v</tex>] '''to''' n)
'''if''' (<tex>vu \in E</tex>)
pushed = dfs(<tex>u</tex>, min(flow, c(<tex>vu</tex>) - f(<tex>vu</tex>)))
f(<tex>uv</tex>) -= pushed
'''return''' pushed
ptr[<tex>v</tex>]++
'''return''' 0
===Асимптотика===
Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <tex>O(K + E_i)</tex> действий, где <tex>K= O(V)</tex> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <tex>E_i</tex> — числу удалённых рёбер. Таким образом, для поиска блокирующего потока будет выполнено <tex>\sum\limits_i{O(K+E_i)} = O(K^2)</tex> действий.
== См. также ==
