Алгоритм Голдберга-Тарьяна — различия между версиями

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

Текущая версия на 22:15, 31 марта 2017

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

Алгоритм[править]

Идея[править]

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

  1. При помощи обхода в глубину находим путь из [math]S[/math] в [math]T[/math].
  2. Находим ребро с минимальной пропускной способностью
  3. Вдоль пути увеличиваем поток на минимальную пропускную способность

Попытаемся ускорить процесс поиска пути из [math]S[/math] в [math]T[/math]. Для этого, для каждой вершины зафиксируем какое-либо, не более, чем одно, исходящее из нее ребро. Граф ацикличен, значит зафиксированные ребра будут образовывать лес корневых деревьев. Корнем каждого дерева будет вершина, у которой нет зафиксированного ребра. В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра.

Желтым выделены зафиксированные ребра. Тогда [math]T[/math] — корень дерева

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

  1. Вычислить минимум на пути от вершины до корня (1).
  2. Прибавить константу к числам на пути от вершины до корня (2).
  3. Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева (3).
  4. Подвесить дерево. Пусть есть дерево с корнем [math]A[/math], дерево с вершиной [math]B[/math]. Операция позволяет Создать ребро из [math]A[/math] в [math]B[/math] и тем самым подвесить дерево к вершине (4).

Заметим, что именно эти операции поддерживает Link-Cut tree и умеет их выполнять за [math]O(\log(N))[/math].

Поиск пути[править]

Научимся находить путь из [math]S[/math] в [math]T[/math] в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.

  • Начало.
  • Шаг 1. Пусть [math]U[/math] — корень дерева, в котором лежит [math]S[/math].
  • Шаг 2. Если вершина [math]U[/math] совпала с вершиной [math]T[/math] переходим к шагу 6, иначе к шагу 3.
  • Шаг 3. Выберем следующее ненасыщенное исходящее ребро. Если ребра нет — переходим к шагу 7. Ребра рассматриваем также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло — больше его не рассматриваем.
  • Шаг 4. Пусть просматриваем ненасыщенное ребро, ведущее в некоторую вершину [math]V[/math]. Подвесим корень [math]U[/math] через это ребро к вершине [math]V[/math], выполнив [math](4)[/math] запрос.
  • Шаг 5. В [math]U[/math] записываем число, равное остаточной пропускной способности ребра. Переходим к шагу 1.
  • Шаг 6. Возвращаем найденный путь.
  • Шаг 7. Пути из [math]S[/math] в [math]T[/math] нет.
  • Конец.

Улучшение пути[править]

Путь из [math]S[/math] в [math]T[/math] найден, теперь научимся улучшать путь. Нужно обновить значения пропускных способностей и потоков через вершины этого пути. Тогда:

  • При помощи [math](1)[/math] запроса можно найти узкое место (ребро с минимальной остаточной пропускной способностью) на этом пути и его пропускную способность.
  • При помощи [math](2)[/math] запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.

Пусть после [math](2)[/math] запроса появилось нулевое ребро. Запрос минимума от [math]S[/math] до корня будет возвращать [math]0[/math]. Поэтому, такие ребра нужно отрезать, выполнив [math](4)[/math] запрос по этому ребру. Стоит заметить, что нулевых ребер может получиться несколько, в случае нескольких минимумов.

Итоговый алгоритм[править]

Объединим вышесказанное в алгоритм Голдберга-Тарьяна. Пусть дана сеть. Требуется в этой сети найти поток [math]f(S, T) [/math] максимальной величины.

  • Начало.
  • Шаг 1. Для каждого ребра [math](u, v)[/math] данной сети [math]G[/math] зададим [math]f(u, v) = 0[/math].
  • Шаг 2. Если есть путь из [math]S[/math] в [math]T[/math] — переходим к шагу 3.
  • Шаг 3. Выполняем [math](1)[/math] запрос, узкое место и пропускную способность. Если пропускная способность положительна, переходим к шагу 4, иначе к шагу 5.
  • Шаг 4. Улучшение пути. Обновляем значения потока и пропускной способности при помощи [math](2)[/math] запроса.
  • Шаг 5. Удаление нулевых ребер. Обрезаем нулевые ребра при помощи [math](3)[/math] запроса. Переходим к шагу 2.
  • Конец.

Время работы[править]

Link-Cut tree выполняет все вышеописанные запросы за [math]O(\log(N))[/math], оценим время работы алгоритма.

Очевидно, что просмотров ребер суммарно [math]O(E)[/math], как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:

  1. Просматриваемое ребро насыщено.
  2. Дерево разрезается по нулевому ребру.
  3. Ребро не лежит в сети кратчайших путей.

На каждый просмотр тратится не [math]O(1)[/math] а [math]O(\log(V))[/math], потому что перед тем, как посмотреть на следующее ребро делается запрос. Значит время работы этой части — [math]O(E \log(V))[/math].

Следующий шаг в алгоритме Диница — сумма длин путей. Раньше считалось за [math]O(V^2)[/math], так как на каждый путь обход в глубину тратил время, пропорциональное длине этого пути. Сейчас тратится только [math]O(\log(V))[/math] на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросу. Поэтому тратим на каждый путь тоже логарифм [math]O(\log(V))[/math].

Тогда имеем ассимптотику [math]O(E\log(V) + V \log(V)) = O((V + E) \log(V))[/math]. И, суммарно, если подставить в алгоритм Диница будем иметь ассимптотику [math]O(VE \log(V)) [/math].

См. также[править]

Источники информации[править]