Изменения

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

==Алгоритм==

Вспомним [[Схема алгоритма Диница|алгоритм Диница]]. Пусть есть сеть <tex>G^0_f </tex> {{---}} некоторый ориентированный ациклический граф, <tex>S</tex>, <tex>T</tex> {{---}} исток и сток соответственно. Схема Алгоритма Диница :

# При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь из <tex>S</tex> в <tex>T</tex>.

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

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

* Будем повторять, пока <tex>S</tex> и <tex>T</tex> не окажутся в одном дереве.

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

* При помощи <tex>(1)</tex> запроса можно найти узкое место (ребро с минимальной остаточной пропускной способностью) на этом пути и его пропускную способность.

Пусть после <tex>(2)</tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Поэтому, такие ребра нужно отрезать, выполнив <tex>(3)</tex> запрос по этому ребру.

Объединим вышесказанное в алгоритм Голдберга-Татьяна.