Редактирование: Алгоритм Голдберга-Тарьяна
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 3: | Строка 3: | ||
==Алгоритм== | ==Алгоритм== | ||
===Идея=== | ===Идея=== | ||
− | Вспомним [[Схема алгоритма Диница|алгоритм Диница]]. Пусть есть сеть <tex>G^0_f </tex> {{---}} некоторый ориентированный ациклический граф, <tex>S</tex>, <tex>T</tex> {{---}} исток и сток соответственно. Схема | + | Вспомним [[Схема алгоритма Диница|алгоритм Диница]]. Пусть есть сеть <tex>G^0_f </tex> {{---}} некоторый ориентированный ациклический граф, <tex>S</tex>, <tex>T</tex> {{---}} исток и сток соответственно. Схема Алгоритма Диница : |
# При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь из <tex>S</tex> в <tex>T</tex>. | # При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь из <tex>S</tex> в <tex>T</tex>. | ||
# Находим ребро с минимальной пропускной способностью | # Находим ребро с минимальной пропускной способностью | ||
Строка 24: | Строка 24: | ||
Научимся находить путь из <tex>S</tex> в <tex>T</tex> в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями. | Научимся находить путь из <tex>S</tex> в <tex>T</tex> в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями. | ||
− | + | Пусть <tex>U</tex> {{---}} корень дерева, в котором лежит <tex>S</tex>. | |
− | + | ||
− | * | + | * Заметим, что если <tex>S</tex>, <tex>T</tex> лежат в одном дереве, то путь ищется легко. Это путь по дереву до корня. |
− | * | + | |
− | + | * Если <tex>S</tex>, <tex>T</tex> лежат в разных деревьях. Просмотрим все ненасыщенные исходящие ребра. Будем рассматривать их также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{---}} больше его не рассматриваем. Пусть просматриваем какое-то ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>: | |
− | + | # Подвесим корень <tex>U</tex> через это ребро к вершине <tex>V</tex>, выполнив запрос (3). | |
− | + | #В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра. | |
− | * | + | |
− | + | * Будем повторять, пока <tex>S</tex> и <tex>T</tex> не окажутся в одном дереве. | |
===Улучшение пути=== | ===Улучшение пути=== | ||
Строка 39: | Строка 39: | ||
* При помощи <tex>(2)</tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку. | * При помощи <tex>(2)</tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку. | ||
− | Пусть после <tex>(2)</tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Поэтому, такие ребра нужно отрезать, выполнив <tex>( | + | Пусть после <tex>(2)</tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Поэтому, такие ребра нужно отрезать, выполнив <tex>(3)</tex> запрос по этому ребру. |
===Итоговый алгоритм=== | ===Итоговый алгоритм=== | ||
− | Объединим вышесказанное в алгоритм Голдберга- | + | Объединим вышесказанное в алгоритм Голдберга-Татьяна. |
Пусть дана сеть. Требуется в этой сети найти поток <tex>f(S, T) </tex> максимальной величины. | Пусть дана сеть. Требуется в этой сети найти поток <tex>f(S, T) </tex> максимальной величины. | ||
− | + | # Для каждого ребра <tex>(u, v)</tex> данной сети <tex>G</tex> зададим <tex>f(u, v) = 0</tex>. | |
− | + | # Пока есть путь из <tex>S</tex> в <tex>T</tex>: | |
− | + | ## Выполняем запрос <tex>(1)</tex>, находим узкое место и пропускную способность. | |
− | + | ## Обновляем значения потока и пропускной способности при помощи запроса <tex>(2)</tex>. | |
− | + | ## Обрезаем нулевые ребра при помощи запроса <tex>(3)</tex>. | |
− | |||
− | |||
==Время работы== | ==Время работы== | ||
− | [[Link-Cut Tree| | + | [[Link-Cut Tree|Linking-Cutting Tree]] выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма. |
Очевидно, что просмотров ребер суммарно <tex>O(E)</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях: | Очевидно, что просмотров ребер суммарно <tex>O(E)</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях: | ||
Строка 66: | Строка 64: | ||
Следующий шаг в алгоритме Диница {{---}} сумма длин путей. Раньше считалось за <tex>O(V^2)</tex>, так как на каждый путь обход в глубину тратил время, пропорциональное длине этого пути. Сейчас тратится только <tex>O(\log(V))</tex> на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросу. Поэтому тратим на каждый путь тоже логарифм <tex>O(\log(V))</tex>. | Следующий шаг в алгоритме Диница {{---}} сумма длин путей. Раньше считалось за <tex>O(V^2)</tex>, так как на каждый путь обход в глубину тратил время, пропорциональное длине этого пути. Сейчас тратится только <tex>O(\log(V))</tex> на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросу. Поэтому тратим на каждый путь тоже логарифм <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> | + | Тогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>. И, суммарно, если подставить в алгоритм Диница будем иметь ассимптотику <tex>O(VE \log(V)) </tex> |
− | == | + | == Смотри также == |
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] | * [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] | ||
* [[Алоритм Эдмондса-Карпа|Алоритм Эдмондса-Карпа]] | * [[Алоритм Эдмондса-Карпа|Алоритм Эдмондса-Карпа]] |