Рассмотрим сеть <tex>G^0_f </tex> {{---}} некоторый ациклический граф, S, T {{---}} исток и сток соответственно. Попытаемся ускорить поиск пути из S в T.
* Для каждой вершины зафиксируем какое-либо, не более чем одно, исходящее из нее ребро. Т.к граф ацикличен, то зафиксированные ребра будут образовывать лес корневых деревьев, где в корне находится вершина, у которой зафиксированного ребра нет.* В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра.
==Linking Cutting trees==В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра. * Пусть каждое дерево поддерживает следующие операции:# Вычисление минимума Вычислить минимум на пути от вершины до корня
# Прибавить константу к числам на пути от вершины до корня.
* Предположим# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева.# Подвесить дерево. Пусть есть дерево с корнем А, дерево с вершиной В. Операция позволяет Создать ребро из A в B и тем самым подвесить дерево к вершине. Теперь предположим, что S, T лежат в одном дереве:# Можно быстро найти пусть из S в T (Пусть Путь по дереву до корня)
# При помощи (1) запроса можно найти узкое место на этом пути.
# При помощи (2) запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, прибавить ее к потоку. (Будем отдельно хранить дерево с потоками и дерево с пропускными способностями)
Но, даже если S и T попали в одно дерево, на следующем шаге запрос минимума, очевидно, выдаст 0. Потому что на предыдущем шаге этот минимум был вычтен и при помощи текущего дерева ничего улучшить уже не удастся. Чтобы решить эту проблему и проблему, когда S и T лежат в разных деревьях, вспомним про (3) и (4) операции и воспользуемся следующим алгоритмом:
Дополнительные операции.
# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева.
# Подвесить дерево. Пусть есть дерево с корнем А, дерево с вершиной В. Операция позволяет Создать ребро из A в B и тем самым подвесить дерево к вершине.
==Алгоритм==
ПредположимЗаметим, что такое дерево существует именно эти операции поддерживает Linking-Cutting Tree и умеет их выполнять все операции за <tex>O(\log(N))</tex> Пусть требуется найти путь из S в T, тогда: # Делаем запрос (1). Получаем корень и расположение минимума до корня.## Если корень {{---}} T, то делаем, как описано выше:### Вычитаем значение минимума из пропускных способностей, прибавляем к потоку.## Иначе### Просматриваем все ненасыщенные исходящие ребра (как и в алгоритме Диница, если просматривали раньше и не подошло, то не рассматриваем больше. Т.е с глобальным итератором, начиная с последнего подошедшего)### Пусть просматриваем какое-то ненасыщеюнное ребро, ведущее в некоторую вершину.### Подвешиваем наше дерево к этому ребру### В бывший корень записываем число, равное остаточной пропускной способности этого ребра. ( Это легко сделать при помощи выполнения (2) операции к самому корню до подвешивания. Пусть было INF, прибавим Value - INF -> PROFIT)Далее, снова пополняем запрос из S... и ТД, пока не доберемся до T.
Хотим найти путь из S в T. Делаем (1) запрос. Получаем корень, минимум до корня, его расположение. Если корень {{---}} T, то делаем как раньше. Иначе: Просматриваем все ненасыщенные исходящие ребра (как и в алгоритме Диница, если просматривали раньше и не подошло, то не рассматриваем больше. Т.е с глобальным итератором, начиная с последнего подошедшего). Пусть просматриваем какое-то ненасыщеюнное ребро, ведущее в некоторую вершину. Подвешиваем наше дерево к этому ребру и в бывший корень записываем число, равное остаточной пропускной способности этого ребра. ( Это легко сделать при помощи выполнения (2) операции к самому корню до подвешивания. Пусть было INF, прибавим Value - INF -> PROFIT).
