Толстые пути и проталкивание предпотока: ещё два способа выжать поток

Если ты знаешь, зачем порог в масштабировании, как устроены высоты и избытки в проталкивании предпотока и почему подъём не ломает корректность, листай до «Теперь сам».

Как думаешь, какой путь выбирать

В уроке про Эдмондса-Карпа неудачный выбор пути превратил два шага в две тысячи: алгоритм гонял по единице через узкое ребро, хотя рядом были пути по тысяче. Кратчайший путь эту беду лечит, но он не смотрит на ёмкости вовсе.

Прежде чем читать дальше, ответь себе: если бы ты разгружал склад вручную, какой маршрут взял бы первым - самый короткий или тот, по которому за раз увезёшь больше всего? И что, если вообще не искать маршруты, а просто открыть все краны и смотреть, куда потечёт?

На что это похоже

Масштабирование - разгрузка от крупного к мелкому: сначала фуры по магистралям, потом грузовики по дорогам, в конце легковушки по дворам. Пока есть магистраль, по дворам не ездят.

Проталкивание предпотока - вода на склоне. Исток - озеро наверху, его открывают целиком. Вода скапливается в ямах (избыток), из ямы течёт только вниз. Если яма оказалась ниже всех соседей и вода стоит, землю под ней поднимают, пока вода не найдёт выход - к стоку или обратно к озеру. Когда вода нигде не стоит, всё, что дошло до стока, и есть максимальный поток.

Механизм: порог и высоты

МАСШТАБИРОВАНИЕ
Δ = наибольшая степень двойки ≤ U
пока Δ ≥ 1:
    пока есть путь s → t по рёбрам с остаточным запасом ≥ Δ:
        пустить по нему минимум
    Δ = Δ / 2
на пороге Δ дополнений не больше 2E: после предыдущего порога
до максимума осталось меньше 2E·Δ, а каждый путь даёт ≥ Δ

ПРОТАЛКИВАНИЕ ПРЕДПОТОКА
высота h(s) = V, остальные 0;  все рёбра из s насыщены сразу
избыток(v) = пришло − ушло  (у промежуточных может быть > 0)
пока есть вершина u ≠ s, t с избытком:
    есть ребро u → v с запасом и h(u) = h(v) + 1:
        протолкнуть min(избыток, запас)
    иначе:
        поднять: h(u) = 1 + min h(v) по рёбрам u → v с запасом

Почему проталкивание верно. Инвариант: у каждого ребра с остаточным запасом u → v выполнено h(u) ≤ h(v) + 1. Высота истока V, стока 0, а путь в остаточной сети из s в t спустился бы по высоте на V за меньше чем V рёбер - невозможно. Значит, пути s → t в остаточной сети нет никогда, и когда избытков не осталось, предпоток стал потоком - и он максимален. Подъём держит инвариант: вершину поднимают ровно до уровня, на единицу выше самого низкого соседа по рёбрам с запасом. Высоты не превосходят 2V, отсюда оценки O(V² · E) для любого порядка и O(V³) для очереди.

Третий путь ускорения - динамические деревья: структура, которая хранит лес путей и умеет за O(log V) найти узкое ребро на пути к корню и вычесть из всего пути разом. С ней блокирующий поток Диница считается за O(E · log V), а весь алгоритм - за O(V · E · log V). Устроена она сложно, и в обычной практике её заменяет хорошо реализованное проталкивание.

Правило

Масштабирование ищет дополняющие пути только с запасом не меньше порога Δ и делит порог пополам: не больше 2E путей на порог, O(E² · log U) в целом. Проталкивание предпотока насыщает рёбра из истока, держит избытки в вершинах и сталкивает их на одну ступень вниз по высотам; вершину без выхода поднимает на единицу выше самого низкого доступного соседа. Остаточный путь s → t невозможен всё время, поэтому без избытков поток максимален; с очередью - O(V³).

Разбор: проталкивание на четырёх вершинах

s→a 3   s→b 2   a→b 1   a→t 2   b→t 3          V = 4

старт: h(s) = 4. Выливаем: s→a 3, s→b 2.  избыток a 3, b 2
a: h(a) = 0, вниз некуда → подъём:
      рёбра с запасом: a→b (h 0), a→t (h 0), a→s (h 4)  → h(a) = 1
   a→b: 1   (избыток b стал 3)
   a→t: 2   (избыток a 0)
b: h(b) = 0 → подъём: b→t (h 0), b→a (h 1), b→s (h 4) → h(b) = 1
   b→t: 3   (избыток b 0)
избытков нет. В t пришло 2 + 3 = 5

Ответ 5 совпадает с разрезом из рёбер истока 3 + 2. Ни одного пути алгоритм не искал: он видел только вершину с избытком и её соседей.

Разбор: четыре способа на одной сети

Программа строит сеть из 120 вершин и полутора тысяч рёбер с ёмкостями до миллиона и считает максимальный поток четырьмя способами: дополнением по любому пути (обход в глубину), по кратчайшему, по толстому и проталкиванием предпотока.

import random
from collections import deque

rng = random.Random(19)
V, s, t = 120, 0, 119
cap0 = [[0] * V for _ in range(V)]
for _ in range(1500):
    u, v = rng.randrange(V), rng.randrange(V)
    if u != v:
        cap0[u][v] += rng.randint(1, 10 ** 6)


def najti_put(cap, porog, vglub):     # путь с запасом ≥ порога
    otec, spisok = {s: None}, deque([s])
    while spisok:                     # стек - любой путь, очередь -
        u = spisok.pop() if vglub else spisok.popleft()   # кратчайший
        for v in range(V):
            if cap[u][v] >= porog and v not in otec:
                otec[v] = u
                if v == t:
                    return otec
                spisok.append(v)
    return None


def dopolnyat(porog, vglub=False):    # порог 1 - обычный алгоритм,
    cap = [row[:] for row in cap0]    # большой порог - масштабирование
    znach = putej = 0
    while porog >= 1:
        while (otec := najti_put(cap, porog, vglub)) is not None:
            put, v = [], t
            while otec[v] is not None:
                put.append((otec[v], v))
                v = otec[v]
            d = min(cap[u][v] for u, v in put)
            for u, v in put:
                cap[u][v] -= d
                cap[v][u] += d
            znach, putej = znach + d, putej + 1
        porog //= 2
    return znach, putej


def predpotok():                      # проталкивание, очередь FIFO
    cap = [row[:] for row in cap0]
    h, izb = [0] * V, [0] * V
    h[s] = V
    for v in range(V):                # исток выливает всё, что может
        if cap[s][v]:
            izb[v] += cap[s][v]
            cap[v][s] += cap[s][v]
            cap[s][v] = 0
    och = deque(v for v in range(V) if izb[v] and v != t)
    operacij = 0
    while och:
        u = och.popleft()
        while izb[u] > 0:
            for v in range(V):        # протолкнуть вниз на одну ступень
                if izb[u] and cap[u][v] and h[u] == h[v] + 1:
                    d = min(izb[u], cap[u][v])
                    cap[u][v] -= d
                    cap[v][u] += d
                    izb[u] -= d
                    izb[v] += d
                    operacij += 1
                    if v not in (s, t) and izb[v] == d:
                        och.append(v)
            if izb[u]:                # некуда - поднять вершину
                h[u] = 1 + min(h[v] for v in range(V) if cap[u][v])
                operacij += 1
    return izb[t], operacij


U = max(max(r) for r in cap0)
a, p0 = dopolnyat(1, vglub=True)
b, p1 = dopolnyat(1)
c, p2 = dopolnyat(2 ** (U.bit_length() - 1))
d, op = predpotok()
assert a == b == c == d
print("величина потока:", a)
print("любой путь (в глубину): путей", p0)
print("кратчайший (Эдмондс-Карп): путей", p1)
print("толстый (масштабирование): путей", p2)
print("предпоток: проталкиваний и подъёмов", op)

величина потока: 4625186
любой путь (в глубину): путей 168
кратчайший (Эдмондс-Карп): путей 27
толстый (масштабирование): путей 16
предпоток: проталкиваний и подъёмов 603

Все четыре дали 4 625 186. Любой путь потребовал 168 дополнений, кратчайший - 27, толстый - 16: толстые пути с первых шагов забирают основную массу потока, и на мелких порогах остаётся добрать немного. Проталкивание сделало 603 локальные операции - каждая дешевле поиска пути, который просматривает всю сеть.

Что ломается без этого

Первая ошибка - в масштабировании начать с порога меньше наибольшей ёмкости по степени двойки и потерять гарантию числа путей на порог - или забыть закончить порогом 1, оставив поток недодобранным. Вторая - в проталкивании толкать в соседа той же высоты или выше: инвариант ломается, появляется остаточный путь s → t, и ответ перестаёт быть максимальным. Третья - поднимать вершину «на единицу», а не до уровня выше самого низкого доступного соседа: алгоритм останется верным, но сделает лишние круги. Четвёртая - ждать, что избыток всегда дойдёт до стока: часть его возвращается в исток, и это нормально - так предпоток избавляется от того, что пролить было некуда.

Зачем это в работе

Проталкивание предпотока с эвристиками (глобальный пересчёт высот, работа с самыми высокими вершинами) - основной алгоритм в библиотеках для больших плотных сетей: сегментация изображений через минимальный разрез, где у каждого пикселя рёбра к соседям, задачи о назначении с огромными графами, расчёт пропускной способности сетей. Масштабирование - общий приём, а не только для потоков: «сначала грубо, по большим числам, потом уточняем» работает в кратчайших путях, в задаче о назначениях и в алгоритмах для целых чисел, когда цена зависит от log U, а не от самих чисел.

Теперь сам

Сеть: s→a 100, a→t 100, s→b 100, b→t 100, a→b 1. Сколько путей найдёт масштабирование и какие пороги ему понадобятся?