Изменения
Нет описания правки
'''Алгоритм Голдберга-Тарьяна''' (англ ''Goldberg-Tarjan'') - алгоритм, решающий задачу нахождения максимального потока в транспортной сети за <tex>O(VE \log(VE))</tex>.
==Linking Cutting trees==
Пусть есть лес деревьев. Каждая вершина знает своих родителей. Во всех вершинах записаны числа.
Требуется структура данных, которую будем использовать для поиска блокирующего потока, которая может выполнять следующие операции:
# Нахождение минимума на пути от вершины до корня
# Прибавление константы на пути ото вершины до корня
# link. Пусть есть дерево с корнем А, дерево с вершиной В. Операция позволяет "подвесить" первое дерево ко второму, т.е создать ребро из А в В.
# cut. Для некоторой выбранной вершины обрезать ребро от нее к ее родителю, сделав ее новым корнем. При этом отрезанное поддерево отделяется и существует независимо от исходного дерева.
===Пути===
Научимся поддерживать эти операции для путей.
# Нахождение минимума на пути от вершины до конца пути
# Прибавление константы на пути ото вершины до корня
# link. Чтобы не образовались деревья, нужно подвешивать путь строго к концу другого пути.
# cut. По вершине обрезаем ребро. Получатся 2 независимых друг от друга пути.
первые две операции - для поиска удлиняющего пути из S в T.
Пусть нет операций link, cut. Все пути статичные, остаются 2 операции:
# Минимум на суффиксе
# Прибавление константы на суффиксе.
Можно использовать дерево отрезков (<tex>O(\log(N))</tex>)
Для cut и link можно использовать Декартовы деревья или Splay-деревья, операции также за <tex>O(\log(N))</tex>. Merge = link, split = cut.
Совместим два концепта.
Возьмем декартовы деревья и добавим к ним функциональность деревьев отрезков. Пусть есть массив 0..n, декартово дерево по неявному ключу для него. Давайте хранить в каждой вершине минимум в поддереве, вычисляется как минимум значений в поддеревьях и значения в вершине. Будем поддерживать при split и merge. Легко узнать минимум на суффиксе: делаем сплит по вершине, берем минимум в нем. Если не хотим портить исходное дерево, то можно либо сделать обратно merge или использовать персистентное дерево, создать новое и потом удалить, чтоб сэкономить память.
Прибавление константы.
Храним модификатор в вершине, который говорит что ко всем узлам в подтерев нужно прибавить константу. ЕГо можно аналогично поддерживать при split и merge. Как прибавляем на суффиксе? Делаем split по вершине, прибавляем модификатор, делаем merge.
Как только в вершине что-то поменялось связанное с детьми, то в ней сразу же пересчитывается все идентификаторы.
Научились делать делать для путей. Обе операции за log(n)
===Деревья===
Проблема в том, что дерево не путь и его нельзя так просто свести к структурам данных, в силу нелинейности индексов. Но можно дерево нарезать на пути. Рассмотрим корневое дерево, на котором хотим выполнять операции. Забудем про (link), (cut). Только первые 2 операции.
==Идея==
