Потоки. Бонусная часть. (25 сентября 2017)
- Техника предпотоков (preflow)
- Определение предпотока, избытка, высот. Операции push и relabel.
- Общий процесс толкания предпотока: пока можно, делаем одну из операций
- Число операций: для каждой вершины не более 2V подъёмов.
- Быстрый процесс толкания предпотока: у каждой вершины поддерживается указатель на текущее ребро head[v]
- Время работы: указатели в сумме пройдут O(VE), подъёмы в сумме отработают за O(VE). Единственная проблема − ненасыщающие операции push.
- Реализации
- Самая простая: O(V3) − round robin, перебираем все вершины по кругу, φ = "максимальная высота избытка".
- Ahuja (масштабирование): O(V2logU + VE) − VE за все фазы на подъёмы вершин.
- Highest level optimization: O(V2E1/2), φ = "максимальная высота избытка" + ∑i,j : ex[i]>0,ex[j]>0 (h[i] ≥ h[j]).
- Global relabeling: не асимптотическая, по факту даёт ≈O(VE)
- Простая и быстрая реализация Global relabeling = bfs за O(E) + перебор всех рёбер в порядке убывания высот за O(E)