Потоки. Бонусная часть. (25 сентября 2017)

1. Техника предпотоков (preflow)
1. Определение предпотока, избытка, высот. Операции push и relabel.
2. Общий процесс толкания предпотока: пока можно, делаем одну из операций
3. Число операций: для каждой вершины не более 2V подъёмов.
4. Быстрый процесс толкания предпотока: у каждой вершины поддерживается указатель на текущее ребро head[v]
5. Время работы: указатели в сумме пройдут O(VE), подъёмы в сумме отработают за O(VE). Единственная проблема − ненасыщающие операции push.


2. Реализации
1. Самая простая: O(V³) − round robin, перебираем все вершины по кругу, φ = "максимальная высота избытка".
2. Ahuja (масштабирование): O(V²logU + VE) − VE за все фазы на подъёмы вершин.
3. Highest level optimization: O(V²E^1/2), φ = "максимальная высота избытка" + ∑_{i,j : ex[i]>0,ex[j]>0} (h[i] ≥ h[j]).
4. Global relabeling: не асимптотическая, по факту даёт ≈O(VE)
5. Простая и быстрая реализация Global relabeling = bfs за O(E) + перебор всех рёбер в порядке убывания высот за O(E)