Масштабирование потока (capacity scaling) — зачем нужно и как ускоряет Форда-Фалкерсона?

Идея масштабирования. Наивный Форд-Фалкерсон плох, когда пропускные большие: он может пускать поток по «тонким» путям много раз. Scaling заставляет алгоритм сначала работать только с толстыми рёбрами.

Заводим порог $\Delta$, начиная с наибольшей степени двойки $\le \max cap$. На каждой «фазе масштабирования»:

• ищем увеличивающие пути, используя только рёбра с остаточной пропускной $\ge \Delta$;
• когда таких путей не осталось — делим $\Delta$ пополам и повторяем;
• заканчиваем, когда $\Delta < 1$.

Так мы сначала «грубо» набираем поток крупными порциями, потом уточняем. Это гарантирует, что число увеличивающих путей в каждой фазе ограничено $O(E)$.

Асимптотика: $O(E^2 \log U)$, где $U = \max cap$. Это убирает зависимость от величины потока (в отличие от наивного $O(E\cdot\text{flow})$) и заменяет её логарифмом от максимальной пропускной — отлично при больших cap и небольшом числе рёбер.

// внутри Форд-Фалкерсона с DFS:
for(long long D = highestPowerOfTwo(maxCap); D >= 1; D >>= 1){
    while(dfs_with_threshold(s, t, D)) // ищет путь с остатками >= D
        ; // пускаем поток
}

Стоит ли писать на олимпиаде? Обычно нет: Диниц ($O(V^2E)$, а на единичных ещё лучше) на практике быстрее и его реализация привычнее. Scaling полезно знать концептуально и для теоретических оценок, а также для некоторых вариантов min-cost flow (cost scaling). Но как рабочую лошадку для max-flow держите Диница.