Алгоритм Голдберга-Тарьяна

Алгоритм Голдберга-Тарьяна (англ Goldberg-Tarjan) - алгоритм, решающий задачу нахождения максимального потока в транспортной сети за [math]O(VE \log(VE))[/math].

Linking Cutting trees

Пусть есть лес деревьев. Каждая вершина знает своих родителей. Во всех вершинах записаны числа. Требуется структура данных, которую будем использовать для поиска блокирующего потока, которая может выполнять следующие операции:

1. Нахождение минимума на пути от вершины до корня
2. Прибавление константы на пути ото вершины до корня
3. link. Пусть есть дерево с корнем А, дерево с вершиной В. Операция позволяет "подвесить" первое дерево ко второму, т.е создать ребро из А в В.
4. cut. Для некоторой выбранной вершины обрезать ребро от нее к ее родителю, сделав ее новым корнем. При этом отрезанное поддерево отделяется и существует независимо от исходного дерева.

Пути

Научимся поддерживать эти операции для путей.

1. Нахождение минимума на пути от вершины до конца пути
2. Прибавление константы на пути ото вершины до корня
3. link. Чтобы не образовались деревья, нужно подвешивать путь строго к концу другого пути.
4. cut. По вершине обрезаем ребро. Получатся 2 независимых друг от друга пути.

первые две операции - для поиска удлиняющего пути из S в T.

Пусть нет операций link, cut. Все пути статичные, остаются 2 операции:

1. Минимум на суффиксе
2. Прибавление константы на суффиксе.

Можно использовать дерево отрезков ([math]O(\log(N))[/math])

Для cut и link можно использовать Декартовы деревья или Splay-деревья, операции также за [math]O(\log(N))[/math]. Merge = link, split = cut.

Совместим два концепта. Возьмем декартовы деревья и добавим к ним функциональность деревьев отрезков. Пусть есть массив 0..n, декартово дерево по неявному ключу для него. Давайте хранить в каждой вершине минимум в поддереве, вычисляется как минимум значений в поддеревьях и значения в вершине. Будем поддерживать при split и merge. Легко узнать минимум на суффиксе: делаем сплит по вершине, берем минимум в нем. Если не хотим портить исходное дерево, то можно либо сделать обратно merge или использовать персистентное дерево, создать новое и потом удалить, чтоб сэкономить память. Прибавление константы. Храним модификатор в вершине, который говорит что ко всем узлам в подтерев нужно прибавить константу. ЕГо можно аналогично поддерживать при split и merge. Как прибавляем на суффиксе? Делаем split по вершине, прибавляем модификатор, делаем merge.

Как только в вершине что-то поменялось связанное с детьми, то в ней сразу же пересчитывается все идентификаторы.

Научились делать делать для путей. Обе операции за log(n)

Деревья

Проблема в том, что дерево не путь и его нельзя так просто свести к структурам данных, в силу нелинейности индексов. Но можно дерево нарезать на пути. Рассмотрим корневое дерево, на котором хотим выполнять операции. Забудем про (link), (cut). Только первые 2 операции.

Идея

Рассмотрим Алгоритм Диница. Его схема такова:

1. При помощи обхода в глубину находим путь.
2. Вдоль него увеличиваем потом на минимальную пропускную способность

Рассмотрим сеть [math]G^0_f [/math] — некоторый ациклический граф, S, T — исток и сток соответственно. Попытаемся ускорить поиск пути из S в T.

• Для каждой вершины зафиксируем какое-либо, не более чем одно, исходящее из нее ребро. Т.к граф ацикличен, то зафиксированные ребра будут образовывать лес корневых деревьев, где в корне находится вершина, у которой зафиксированного ребра нет.
• В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра.

Linking Cutting trees

• Пусть каждое дерево поддерживает следующие операции:

1. Вычисление минимума на пути от вершины до корня
2. Прибавить константу к числам на пути от вершины до корня.

• Предположим, что S, T лежат в одном дереве:

1. Можно быстро найти пусть из S в T (Пусть по дереву до корня)
2. При помощи (1) запроса можно найти узкое место на этом пути.
3. При помощи (2) запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, прибавить ее к потоку. (Будем отдельно хранить дерево с потоками и дерево с пропускными способностями)

Но, даже если S и T попали в одно дерево, на следующем шаге запрос минимума, очевидно, выдаст 0. Потому что на предыдущем шаге этот минимум был вычтен и при помощи текущего дерева ничего улучшить уже не удастся.

Дополнительные операции.

1. Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева.
2. Подвесить дерево. Пусть есть дерево с корнем А, дерево с вершиной В. Операция позволяет Создать ребро из A в B и тем самым подвесить дерево к вершине.

Алгоритм

Предположим, что такое дерево существует и умеет выполнять все операции за [math]O(\log(N))[/math]

Хотим найти путь из S в T. Делаем (1) запрос. Получаем корень, минимум до корня, его расположение. Если корень — T, то делаем как раньше. Иначе: Просматриваем все ненасыщенные исходящие ребра (как и в алгоритме Диница, если просматривали раньше и не подошло, то не рассматриваем больше. Т.е с глобальным итератором, начиная с последнего подошедшего). Пусть просматриваем какое-то ненасыщеюнное ребро, ведущее в некоторую вершину. Подвешиваем наше дерево к этому ребру и в бывший корень записываем число, равное остаточной пропускной способности этого ребра. ( Это легко сделать при помощи выполнения (2) операции к самому корню до подвешивания. Пусть было INF, прибавим Value - INF -> PROFIT).

Далее, снова пополняем запрос из S... и ТД, пока не доберемся до T.

Добрались до T. Делаем операцию улучшения пути, появилось нулевое ребро. Обрезаем его. Продолжаем спрашивать из S. Нулевых ребер может быть несколько, значит нужно предусмотреть и для обычного шага. Если запрос из S до корня дал 0, то нужно это ребро отрезать.

Время работы

Из предположения, что есть структура данных. Просмотров ребра суммарно О(Е), аналогично алгоритму Диница. Переход к следующему, когда смотрим на ребро и оно насыщено, когда ребро разрезаем, когда смотрим на ребро и оно не лежит в сети кратчайших путей. На каждый просмотр тратится не О(1) а О(log), потому что делаем запрос перед тем как посмотреть на следующее ребро. Значит O(E log(V)).

Второй компонент в алг. Диница - сумма длин путей. Была V^2. Почему столько? На каждый путь DFS тратил время, пропорциональное длине этого пути. Но теперь не тратим. Тратим log на каждый путь. Потому что если мы нашли путь, это соответствует тому, что мы дошли до него, т.е одному запросу. Поэтому тратим на каждый путь тоже логарифм. Значит O(E log(V) + V log(V)).