147
правок
Изменения
м
→Алгоритм
Пусть дана сеть. Требуется в этой сети найти поток <tex>f(S, T) </tex> максимальной величины.
# Для каждого ребра <tex>(u, v)</tex> данной сети <tex>G</tex> зададим <tex>f(u, v) = 0</tex>.
# Пока есть путь из <tex>S</tex> в <tex>T</tex>:
## Выполняем запрос <tex>(1)</tex>, находим узкое место и пропускную способность.## Обновляем значения потока и пропускной способности при помощи запроса <tex>(2)</tex>.## Обрезаем нулевые ребра при помощи запроса <tex>(3)</tex>.
==Время работы==
