18
правок
Изменения
м
→Поиск пути: typo
Научимся находить путь из <tex>S</tex> в <tex>T</tex> в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.
* Начало.
* '''Шаг 1'''. Пусть <tex>U</tex> {{---}} корень дерева, в котором лежит <tex>S</tex>.
* '''Шаг 2'''. Если вершина <tex>U</tex> совпала с вершиной <tex>T</tex> переходим к '''шагу 6''', иначе к '''шагу 3'''.
* '''Шаг 3'''. Выберем следующее ненасыщеюнное ненасыщенное исходящее ребро. Если ребра нет {{---}} переходим к '''шагу 7'''. Ребра рассматриваем также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{---}} больше его не рассматриваем.
* '''Шаг 4'''. Пусть просматриваем ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>. Подвесим корень <tex>U</tex> через это ребро к вершине <tex>V</tex>, выполнив <tex>(4)</tex> запрос.
* '''Шаг 5'''. В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра. Переходим к '''шагу 1'''.
* '''Шаг 6'''. Возвращаем найденный путь.
* '''Шаг 7'''. Пути из <tex>S</tex> в <tex>T</tex> нет.
* Конец.
===Улучшение пути===
* При помощи <tex>(2)</tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.
Пусть после <tex>(2)</tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Поэтому, такие ребра нужно отрезать, выполнив <tex>(4)</tex> запрос по этому ребру. Стоит заметить, что нулевых ребер может получиться несколько, в случае нескольких минимумов.
===Итоговый алгоритм===
Пусть дана сеть. Требуется в этой сети найти поток <tex>f(S, T) </tex> максимальной величины.
* Начало.
* '''Шаг 1'''. Для каждого ребра <tex>(u, v)</tex> данной сети <tex>G</tex> зададим <tex>f(u, v) = 0</tex>.
* '''Шаг 2'''. Если есть путь из <tex>S</tex> в <tex>T</tex> {{---}} переходим к '''шагу 3'''.
* '''Шаг 4'''. ''Улучшение пути''. Обновляем значения потока и пропускной способности при помощи <tex>(2)</tex> запроса.
* '''Шаг 5'''. ''Удаление нулевых ребер''. Обрезаем нулевые ребра при помощи <tex>(3)</tex> запроса. Переходим к '''шагу 2'''.
* Конец.
==Время работы==
[[Link-Cut Tree|LinkingLink-Cutting TreeCut tree]] выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма.
Очевидно, что просмотров ребер суммарно <tex>O(E)</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:
Тогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>. И, суммарно, если подставить в алгоритм Диница будем иметь ассимптотику <tex>O(VE \log(V)) </tex>.
== Смотри См. также ==
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа|Алоритм Эдмондса-Карпа]]
