Изменения

Пусть нет операций link, cut. Все пути статичные, остаются 2 операции:

Возьмем декартовы деревья и добавим к ним функциональность деревьев отрезков. Пусть есть массив 0..n, декартово дерево по неявному ключу для него. Давайте хранить в каждой вершине минимум в поддереве, вычисляется как минимум значений в поддеревьях и значения в вершине. Будем поддерживать при split и merge. Легко узнать минимум на суффиксе: делаем сплит по вершине, берем минимум в нем. Если не хотим портить исходное дерево, то можно либо сделать обратно merge или использовать персистентное дерево, создать новое и потом удалить, чтоб сэкономить память.

Рассмотрим Вспомним [[Схема алгоритма Диница|Алгоритм Диница]]. Его схема такова:# При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь.# Вдоль него увеличиваем потом на минимальную пропускную способность  Рассмотрим Пусть есть сеть <tex>G^0_f </tex> {{---}} некоторый ациклический граф, S, T {{---}} исток и сток соответственно. Попытаемся ускорить поиск пути Схема Алгоритма Диница :# При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь из S в T.# Находим ребро с минимальной пропускной способностьюДля каждой вершины зафиксируем какое-либо, не более чем одно, исходящее из нее ребро. Т.к граф ацикличен, то зафиксированные ребра будут образовывать лес корневых деревьев, где в корне находится вершина, у которой зафиксированного ребра нет.# Вдоль пути увеличиваем поток на минимальную пропускную способность

Теперь предположимЗаметим, что если S, T лежат в одном дереве:# Можно быстро , то можно легко найти пусть путь из S в T (Путь по дереву до корня), а тогда:# При помощи (1) запроса можно найти узкое место на этом путии его пропускную способность.# При помощи (2) запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку. (Будем отдельно хранить дерево с потоками и дерево с пропускными способностями).

Но, даже если S и T попали в одно дерево, на следующем шаге запрос минимума, очевидно, выдаст 0. Потому что на предыдущем шаге этот минимум был вычтен и при помощи текущего дерева ничего улучшить уже не удастся.

Просмотров ребра суммарно О(Е), аналогично алгоритму Диница. Переход к следующему, когда смотрим на ребро и оно насыщено, когда ребро разрезаем, когда смотрим на ребро и оно не лежит в сети кратчайших путей.