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