Изменения
Нет описания правки
Пусть есть лес деревьев. Каждая вершина знает своих родителей. Во всех вершинах записаны числа.
Требуется структура данных, которую будем использовать для поиска блокирующего потока, которая может выполнять следующие операции:
Когда есть запрос для какого-то пути, мы сначала перестроим пути так, чтоб путь от вершины до корня был полностью из жирных (solid) ребер.
=Алгоритм Голдберга-Таряна=
'''Алгоритм Голдберга-Тарьяна''' (англ ''Goldberg-Tarjan'') - алгоритм, решающий задачу нахождения максимального потока в транспортной сети за <tex>O(VE \log(VE))</tex>.
==Идея==
Рассмотрим [[Схема алгоритма Диница|Алгоритм Диница]]. Его схема такова:
