1632
правки
Изменения
м
=Linking Cutting trees=
Пусть есть лес деревьев. Каждая вершина знает своих родителей. Во всех вершинах записаны числа.
Требуется структура данных, которую будем использовать для поиска блокирующего потока, которая может выполнять следующие операции:
# Нахождение минимума на пути от вершины до корня
# Прибавление константы на пути ото вершины до корня
# link. Пусть есть дерево с корнем А, дерево с вершиной В. Операция позволяет "подвесить" первое дерево ко второму, т.е создать ребро из А в В.
# cut. Для некоторой выбранной вершины обрезать ребро от нее к ее родителю, сделав ее новым корнем. При этом отрезанное поддерево отделяется и существует независимо от исходного дерева.
первые две операции - для Попытаемся ускорить процесс поиска удлиняющего пути из <tex>S </tex> в <tex>T</tex>. Для этого, для каждой вершины зафиксируем какое-либо, не более, чем одно, исходящее из нее ребро. Граф ацикличен, значит зафиксированные ребра будут образовывать лес корневых деревьев. Корнем каждого дерева будет вершина, у которой нет зафиксированного ребра.В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра.
Пусть нет операций link, cut[[Файл:Голдберг-Тарьян. Все пути статичные, остаются 2 операции: # Минимум на суффиксе# Прибавление константы на суффиксеграф.png |500px |thumb|center| Желтым выделены зафиксированные ребра.Тогда <tex>T</tex> {{---}} корень дерева]]
Можно использовать Пусть каждое дерево отрезков поддерживает следующие операции:# Вычислить минимум на пути от вершины до корня (1).# Прибавить константу к числам на пути от вершины до корня (2).# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева (3).# Подвесить дерево. Пусть есть дерево с корнем <tex>A</tex>O(\log(N)), дерево с вершиной <tex>B</tex>. Операция позволяет Создать ребро из <tex>A</tex> в <tex>B</tex>и тем самым подвесить дерево к вершине (4).
Для cut и link можно использовать Декартовы деревья или Splay-деревьяЗаметим, что именно эти операции также поддерживает [[Link-Cut Tree|Link-Cut tree]] и умеет их выполнять за <tex>O(\log(N))</tex>. Merge = link, split = cut.
Совместим два концепта.===Поиск пути===Возьмем декартовы деревья и добавим к ним функциональность деревьев отрезков. Пусть есть массив 0..n, декартово дерево по неявному ключу для него. Давайте хранить Научимся находить путь из <tex>S</tex> в каждой вершине минимум <tex>T</tex> в поддереве, вычисляется как минимум значений в поддеревьях и значения в вершинеописанной выше сети при помощи леса корневых деревьев. Будем поддерживать при split отдельно хранить дерево с потоками и merge. Легко узнать минимум на суффиксе: делаем сплит по вершине, берем минимум в нем. Если не хотим портить исходное дерево, то можно либо сделать обратно merge или использовать персистентное дерево, создать новое и потом удалить, чтоб сэкономить память. Прибавление константы.Храним модификатор в вершине, который говорит что ко всем узлам в подтерев нужно прибавить константу. ЕГо можно аналогично поддерживать при split и merge. Как прибавляем на суффиксе? Делаем split по вершине, прибавляем модификатор, делаем mergeс пропускными способностями.
Как только * Начало.* '''Шаг 1'''. Пусть <tex>U</tex> {{---}} корень дерева, в вершине чтокотором лежит <tex>S</tex>.* '''Шаг 2'''. Если вершина <tex>U</tex> совпала с вершиной <tex>T</tex> переходим к '''шагу 6''', иначе к '''шагу 3'''.* '''Шаг 3'''. Выберем следующее ненасыщенное исходящее ребро. Если ребра нет {{---то поменялось связанное }} переходим к '''шагу 7'''. Ребра рассматриваем также, как и в алгоритме Диница, с детьмиглобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{---}} больше его не рассматриваем. * '''Шаг 4'''. Пусть просматриваем ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>. Подвесим корень <tex>U</tex> через это ребро к вершине <tex>V</tex>, выполнив <tex>(4)</tex> запрос.* '''Шаг 5'''. В <tex>U</tex> записываем число, то равное остаточной пропускной способности ребра. Переходим к '''шагу 1'''.* '''Шаг 6'''. Возвращаем найденный путь.* '''Шаг 7'''. Пути из <tex>S</tex> в ней сразу же пересчитывается все идентификаторы<tex>T</tex> нет.* Конец.
Научились делать делать для путей===Улучшение пути===Путь из <tex>S</tex> в <tex>T</tex> найден, теперь научимся улучшать путь. Обе операции за logНужно обновить значения пропускных способностей и потоков через вершины этого пути. Тогда:* При помощи <tex>(1)</tex> запроса можно найти узкое место (nребро с минимальной остаточной пропускной способностью)на этом пути и его пропускную способность.* При помощи <tex>(2)</tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.
===Деревья===Проблема в том, что дерево не путь и его нельзя так просто свести к структурам данных, в силу нелинейности индексовПусть после <tex>(2)</tex> запроса появилось нулевое ребро. Но можно дерево нарезать на путиЗапрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Рассмотрим корневое деревоПоэтому, на котором хотим выполнять операции. Забудем про (link)такие ребра нужно отрезать, выполнив <tex>(cut4)</tex> запрос по этому ребру. Только первые 2 операции.Существует подходСтоит заметить, что нулевых ребер может получиться несколько, который позволяет сделать за log(n)^2в случае нескольких минимумов.
Heavy-Light Decomposition.===Итоговый алгоритм===
Рассмотрим дерево, каждое ребро объявим легким и тяжелым по следующему критерию:Пусть есть дерево, у него есть размер - количество вершин Объединим вышесказанное в поддереве. Среди всех поддеревьев дерева выберем самое большое по размеру и ребро из него объявим тяжелым. Если одинаковые алгоритм Голдберга- любое выберемТарьяна. В каждую вершину кроме листа будет входить ровно одно тяжелое ребро из самого большого поддереваПусть дана сеть. Тогда несложно заметитьТребуется в этой сети найти поток <tex>f(S, T) </tex> максимальной величины.
Лемма* Начало. На пути от любой вершины до корня не больше log* '''Шаг 1'''. Для каждого ребра <tex>(u, v)</tex> данной сети <tex>G</tex> зададим <tex>f(Nu, v) легких ребер= 0</tex>.* '''Шаг 2'''. Потому что каждый раз когда мы идем по легкому ребру, размер поддерева той вершины, Если есть путь из <tex>S</tex> в которой мы находимся<tex>T</tex> {{---}} переходим к '''шагу 3'''.* '''Шаг 3'''. Выполняем <tex>(1)</tex> запрос, размер поддерева увеличивается хотя бы в два разаузкое место и пропускную способность. Потому что если увеличился меньшеЕсли пропускная способность положительна, чем в два разапереходим к '''шагу 4''', значит здесь было больше половины потомков следующей вершины, значит это ребро было тяжелыминаче к '''шагу 5'''. Значит легких ребер мало, а тяжелых много* '''Шаг 4'''. Тяжелые ребра образуют разбиение дерева на ''Улучшение пути''. Обновляем значения потока и пропускной способности при помощи <tex>(2)</tex> запроса. Чтобы решить наши задачи делаем так:# Начинаем в какой-то вершине, берем тот путь к которому она принадлежит * '''Шаг 5'''. ''Удаление нулевых ребер''. Обрезаем нулевые ребра при помощи <tex>(Тот фрагмент от вершины до конца тяжелого пути3)</tex> запроса. Переходим к '''шагу 2'''.# Делаем шаг по легкому пути# Берем снова часть тяжелого пути# и т.д, пока не дойдем до корня* Конец.
Тогда запрос на суффиксе пути будет ==Время работы==[[Link-Cut Tree|Link-Cut tree]] выполняет все вышеописанные запросы за <tex>O(\log(N). Каждый раз, когда меняем путь - проходим по легкому пути. Т.к по лемме их не больше log(N)</tex>, то суммарное оценим время запроса log(n)^2. Если добавить link, cut, то тяжело поддерживать, какое ребро легкое какое тяжелое. Жд этого нужно аккуратно следить за деревьями. Потому что при подвешивании дерева, абсолютно любое ребро на пути от вершины до корня может стать легким или тяжелым. Это неудобно. Применим метод как в TANGO-деревьяхработы алгоритма.
Когда есть запрос для какого-то путиОчевидно, мы сначала перестроим пути так, чтоб путь от вершины до корня был полностью из жирных что просмотров ребер суммарно <tex>O(solidE) ребер</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:# Просматриваемое ребро насыщено.# Дерево разрезается по нулевому ребру.# Ребро не лежит в сети кратчайших путей.
=Алгоритм ГолдбергаНа каждый просмотр тратится не <tex>O(1)</tex> а <tex>O(\log(V))</tex>, потому что перед тем, как посмотреть на следующее ребро делается запрос. Значит время работы этой части {{-Таряна='''Алгоритм Голдберга-Тарьяна''' (англ ''Goldberg-Tarjan'') - алгоритм, решающий задачу нахождения максимального потока в транспортной сети за }} <tex>O(VE E \log(VEV))</tex>.==Идея==Рассмотрим [[Схема алгоритма Диница|Алгоритм Диница]]. Его схема такова:# При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь.# Вдоль него увеличиваем потом на минимальную пропускную способность
Рассмотрим сеть Следующий шаг в алгоритме Диница {{---}} сумма длин путей. Раньше считалось за <tex>GO(V^0_f 2)</tex>, так как на каждый путь обход в глубину тратил время, пропорциональное длине этого пути. Сейчас тратится только <tex>O(\log(V))</tex> {{---}} некоторый ациклический графна каждый путь. Если путь найден, Sзначит до него дошли, T {{---}} исток и сток соответственнозначит это соответствует одному запросу. Попытаемся ускорить поиск пути из S в TПоэтому тратим на каждый путь тоже логарифм <tex>O(\log(V))</tex>.
* Для каждой вершины зафиксируем какое-либо, не более чем одно, исходящее из нее реброТогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>. Т.к граф ацикличенИ, то зафиксированные ребра будут образовывать лес корневых деревьевсуммарно, где если подставить в корне находится вершина, у которой зафиксированного ребра нет.* В каждой вершине алгоритм Диница будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребраиметь ассимптотику <tex>O(VE \log(V)) </tex>.
Но, даже если S и T попали в одно дерево, на следующем шаге запрос минимума, очевидно, выдаст 0. Потому что на предыдущем шаге этот минимум был вычтен и при помощи текущего дерева ничего улучшить уже не удастся. Дополнительные операции.# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева.# Подвесить дерево. Пусть есть дерево с корнем А, дерево с вершиной В. Операция позволяет Создать ребро из A в B и тем самым подвесить дерево к вершине.==АлгоритмИсточники информации ==Предположим, что такое дерево существует и умеет выполнять все операции за <tex>O(\log(N))<*[https://tex> Хотим найти путь из S в Twww. Делаем (1) запросlektorium. Получаем корень, минимум до корня, его расположение. Если корень tv/lecture/14408 Lektorium {{---}} 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)).[[Категория: Алгоритмы и структуры данных]][[Категория: Задача о максимальном потоке ]]
rollbackEdits.php mass rollback
'''Алгоритм Голдберга-Тарьяна''' (англ. ''Goldberg-Tarjan'') {{---}} алгоритм, решающий задачу нахождения максимального потока в транспортной сети за <tex>O(VE \log(V))</tex>. Можно считать модификацией алгоритма Диница.==Алгоритм===Пути==Идея===Научимся поддерживать эти операции для путейВспомним [[Схема алгоритма Диница|алгоритм Диница]].Пусть есть сеть <tex>G^0_f </tex> {{---}} некоторый ориентированный ациклический граф, <tex>S</tex>, <tex>T</tex> {{---}} исток и сток соответственно. Схема алгоритма Диница:# Нахождение минимума на пути от вершины до конца пути# Прибавление константы на пути ото вершины до корня# link. Чтобы не образовались деревьяПри помощи [[Обход в глубину, нужно подвешивать цвета вершин|обхода в глубину]] находим путь строго к концу другого путииз <tex>S</tex> в <tex>T</tex>.# cut. По вершине обрезаем Находим ребро. Получатся 2 независимых друг от друга с минимальной пропускной способностью# Вдоль пути.увеличиваем поток на минимальную пропускную способность
==Linking Cutting treesСм. также ==* Пусть каждое дерево поддерживает следующие операции:# Вычисление минимума на пути от вершины до корня# Прибавить константу к числам на пути от вершины до корня.* Предположим[[Алгоритм Форда-Фалкерсона, что Sреализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, T лежат реализация с помощью поиска в одном дереве:глубину]]# Можно быстро найти пусть из S в T (Пусть по дереву до корня)* [[Алоритм Эдмондса-Карпа|Алоритм Эдмондса-Карпа]]# При помощи (1) запроса можно найти узкое место на этом пути.* [[Алгоритм масштабирования потока|Алгоритм масштабирования потока]]# При помощи (2) запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, прибавить ее к потоку. (Будем отдельно хранить дерево с потоками и дерево с пропускными способностями)* [[Метод проталкивания предпотока|Метод проталкивания предпотока]]
