147
правок
Изменения
Нет описания правки
Попытаемся ускорить процесс поиска пути из <tex>S</tex> в <tex>T</tex>. Для этого, для каждой вершины зафиксируем какое-либо, не более, чем одно, исходящее из нее ребро. Граф ацикличен, значит зафиксированные ребра будут образовывать лес корневых деревьев. Корнем каждого дерева будет вершина, у которой нет зафиксированного ребра.
В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра.
Пусть каждое дерево поддерживает следующие операции:
# Прибавить константу к числам на пути от вершины до корня.
# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева.
# Подвесить дерево. Пусть есть дерево с корнем <tex>АA</tex>, дерево с вершиной <tex>ВB</tex>. Операция позволяет Создать ребро из <tex>A</tex> в <tex>B</tex> и тем самым подвесить дерево к вершине.
Заметим, что именно эти операции поддерживает [[Link-Cut Tree|Linking-Cutting Tree]] и умеет их выполнять за <tex>O(\log(N))</tex>
