147
правок
Изменения
Нет описания правки
'''Алгоритм Голдберга-Тарьяна''' (англ ''Goldberg-Tarjan'') - алгоритм, решающий задачу нахождения максимального потока в транспортной сети за <tex>O(VE \log(VE))</tex>. Можно считать модификацией Алгоритма Диница.
==Идея==
Вспомним [[Схема алгоритма Диница|Алгоритм Диница]]. Пусть есть сеть <tex>G^0_f </tex> {{---}} некоторый ациклический граф, <tex>S</tex>, <tex>T </tex> {{---}} исток и сток соответственно. Схема Алгоритма Диница :# При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь из <tex>S </tex> в <tex>T</tex>.
# Находим ребро с минимальной пропускной способностью
# Вдоль пути увеличиваем поток на минимальную пропускную способность
Попытаемся ускорить процесс поиска пути из <tex>S </tex> в <tex>T</tex>. Для этого, для каждой вершины зафиксируем какое-либо, не более, чем одно, исходящее из нее ребро. Граф ацикличен, значит зафиксированные ребра будут образовывать лес корневых деревьев. Корнем каждого дерева будет вершина, у которой нет зафиксированного ребра.
В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра.
# Прибавить константу к числам на пути от вершины до корня.
# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева.
# Подвесить дерево. Пусть есть дерево с корнем <tex>А</tex>, дерево с вершиной <tex>В</tex>. Операция позволяет Создать ребро из <tex>A </tex> в <tex>B </tex> и тем самым подвесить дерево к вершине.
Заметим, что именно эти операции поддерживает [[Link-Cut Tree|Linking-Cutting Tree]] и умеет их выполнять за <tex>O(\log(N))</tex>
==Поиск пути==
Научимся находить путь из <tex>S </tex> в <tex>T </tex> в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.
Пусть <tex>U </tex> {{- --}} корень дерева, в котором лежит <tex>S</tex>.
* Заметим, что если <tex>S</tex>, <tex>T </tex> лежат в одном дереве, то путь ищется легко. Это путь по дереву до корня.
* Если <tex>S</tex>, <tex>T </tex> лежат в разных деревьях. Просмотрим все ненасыщенные исходящие ребра. Будем рассматривать их также, как и в Алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло - больше его не рассматриваем. Пусть просматриваем какое-то ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>:# Подвесим корень <tex>U </tex> через это ребро к вершине V (Операция 3). #В <tex>U </tex> записываем число, равное остаточной пропускной способности ребра.
* Будем повторять, пока <tex>S </tex> и <tex>T </tex> не окажутся в одном дереве.
==Улучшение пути==
Путь из <tex>S </tex> в <tex>T </tex> найден, теперь научимся улучшать путь. Нужно обновить значения пропускных способностей и потоков через вершины этого пути. Тогда:# При помощи <tex>(1) </tex> запроса можно найти узкое место на этом пути и его пропускную способность.# При помощи <tex>(2) </tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.
Пусть после <tex>(2) </tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S </tex> до корня будет возвращать 0. Поэтому, такие ребра нужно отрезать, выполнив <tex>(4) </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>(4)</tex>
==Время работы==
