Остовные деревья и потоки в сетях

Есть класс задач, который выглядит как «геометрия на графе»: соединить всё дёшево, пропихнуть как можно больше, разрезать как можно дешевле, распределить как можно справедливее. Все они про сеть как ресурс, а не про сеть как схему связности. Это качественно другой уровень по сравнению с обходами из статьи Обходы графов и даже с кратчайшими путями из Кратчайшие пути: там мы искали маршрут, здесь мы ищем структуру целиком — подмножество рёбер, которое оптимально по глобальному критерию.

Две темы этой статьи — MST и потоки — на первый взгляд не связаны. На самом деле связь глубокая:

• MST — это торжество жадности. Задача устроена так, что локально верный выбор никогда не приходится отменять. За этим стоит теория матроидов (см. Жадные алгоритмы).
• Потоки — это то, что происходит, когда жадность не работает, и её приходится чинить. Механизм починки — обратные рёбра остаточной сети — одна из самых красивых идей в алгоритмике, и её стоит понять до кости, потому что она переиспользуется везде: в паросочетаниях, в min-cost flow, в венгерском алгоритме, в симплекс-методе на сетях.

Плюс потоки — это чемпион по моделированию. Огромное число практических задач, не выглядящих как «трубы и вода», сводятся к максимальному потоку за 20 строк построения графа. Умение увидеть это сведение — навык, который окупается больше, чем знание самого алгоритма.

Часть I. Минимальное остовное дерево

Постановка и зачем

Дан связный неориентированный граф G = (V, E) с весами рёбер w: E → ℝ. Нужно выбрать подмножество рёбер T ⊆ E, которое:

1. соединяет все вершины (остовное — spanning),
2. не содержит циклов (дерево, ровно |V| - 1 рёбер),
3. минимально по суммарному весу.

Каноническая мотивация — прокладка кабеля между офисами: соединить все точки, потратив минимум провода. Но настоящая ценность MST в том, что он оказался фундаментальным структурным объектом:

• Кластеризация. Удалите из MST k-1 самых тяжёлых рёбер — получите ровно кластеризацию single-linkage на k кластеров, причём оптимальную по критерию «максимизировать минимальный зазор между кластерами». Это не эвристика, это теорема.
• Минимаксные пути. Путь между u и v в MST минимизирует максимальное ребро на пути (bottleneck path). Задача «проехать по мостам с максимальной грузоподъёмностью» решается MST.
• Приближения. MST даёт 2-приближение метрической задачи коммивояжёра, а с трюком Кристофидеса — 1.5 (см. NP-полнота и приближения).
• Сегментация изображений (Felzenszwalb–Huttenlocher), построение сетевых топологий, анализ филогенетических деревьев в биоинформатике.

Два свойства, из которых следует всё

Практически все алгоритмы MST — частные случаи одного жадного мета-алгоритма, а его корректность держится на двух утверждениях.

Свойство разреза (cut property). Пусть (S, V\S) — произвольный разрез (разбиение вершин на две непустые части). Пусть e — ребро минимального веса среди всех, пересекающих разрез. Тогда e содержится в некотором MST. Если минимум уникален — e содержится во всех MST.

Доказательство — стандартный аргумент обмена. Возьмём любое MST T, не содержащее e = (u, v). Добавим e в T — образуется ровно один цикл. Этот цикл начинается в S, кончается в S, значит пересекает разрез чётное число раз, то есть содержит ещё хотя бы одно пересекающее ребро f ≠ e. По выбору e имеем w(e) ≤ w(f). Заменим f на e: снова остовное дерево, вес не увеличился. Значит, MST с e существует. ∎

Свойство цикла (cycle property). Если e — строго максимальное по весу ребро некоторого цикла, то e не входит ни в одно MST. Доказательство симметричное: удалив e из дерева, мы разбиваем его на две компоненты, а остальные рёбра цикла обязательно соединяют их обратно ребром меньшего веса.

Эти два свойства — «красящий» мета-алгоритм Тарьяна: cut property разрешает красить ребро синим (взять), cycle property — красным (выбросить). Любой порядок применений даёт MST. Крускал, Прим и Борувка — просто разные расписания этих покрасок.

Важный нюанс про уникальность. Если все веса рёбер попарно различны, MST единственно. Если есть равные веса, MST может быть несколько, и разные алгоритмы (и даже разные реализации сортировки) дадут разные ответы. Это регулярный источник «нестабильных» тестов: сумма совпадает, а множество рёбер — нет. Сравнивайте суммарный вес, а не список рёбер.

Алгоритм Крускала

Идея: отсортировать рёбра по возрастанию веса и жадно добавлять те, что не создают цикл. Проверка «создаёт ли цикл» — это в точности вопрос «лежат ли концы в одной компоненте», то есть система непересекающихся множеств (DSU / union-find).

KRUSKAL(V, E):
    отсортировать E по возрастанию веса
    dsu = DSU(|V|)
    T = ∅
    для каждого (u, v, w) из E:
        если dsu.find(u) ≠ dsu.find(v):
            dsu.union(u, v)
            T = T ∪ {(u, v, w)}
    вернуть T

Корректность: когда мы рассматриваем ребро (u, v), оно минимально среди всех ещё не рассмотренных; возьмём разрез, отделяющий компоненту u от остального графа. Все рёбра, пересекающие этот разрез и имеющие меньший вес, уже были рассмотрены и отвергнуты (иначе они бы соединили компоненты). Значит (u, v) — минимальное пересекающее ребро, и cut property разрешает его взять.

class DSU:
    """Система непересекающихся множеств: сжатие путей + объединение по размеру.
    Амортизированная сложность операции — O(α(n)), обратная функция Аккермана (< 5 на практике)."""

    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x: int) -> int:
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        # второй проход — сжатие путей до корня
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a: int, b: int) -> bool:
        a, b = self.find(a), self.find(b)
        if a == b:
            return False                    # уже вместе — ребро создало бы цикл
        if self.size[a] < self.size[b]:     # меньшее дерево вешаем на большее
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.components -= 1
        return True


def kruskal(n: int, edges: list[tuple[int, int, int]]):
    """edges — список (u, v, вес). Возвращает (рёбра MST, суммарный вес)
    или (None, None), если граф несвязный.
    Время: O(E log E) на сортировку, O(E α(V)) на DSU. Память: O(V + E)."""
    dsu = DSU(n)
    mst, total = [], 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if dsu.union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:           # дерево собрано, дальше смотреть незачем
                break
    return (mst, total) if dsu.components == 1 else (None, None)

Сложность. O(E log E) = O(E log V) (потому что E ≤ V², значит log E ≤ 2 log V). Доминирует сортировка. Если веса — небольшие целые, замените сортировку на radix sort (см. Сортировки) и получите O(E α(V)) — практически линейно. Если рёбра уже отсортированы (например, приходят из потока данных) — тоже линейно.

Алгоритм Прима

Идея другая: растим одно дерево из стартовой вершины, каждый раз добавляя самое лёгкое ребро, выходящее из уже построенного дерева наружу. Это буквально cut property, применённое к разрезу «дерево / всё остальное».

import heapq


def prim(n: int, adj: list[list[tuple[int, int]]], start: int = 0):
    """adj[v] — список (сосед, вес). «Ленивая» версия: вместо decrease-key
    кладём дубликаты в кучу и отбрасываем устаревшие при извлечении.
    Время: O(E log E). Память: O(E) — куча может содержать до E элементов."""
    visited = [False] * n
    heap = [(0, start, -1)]                 # (вес ребра, вершина, откуда пришли)
    mst, total = [], 0
    while heap:
        w, v, parent = heapq.heappop(heap)
        if visited[v]:                      # устаревшая запись — пропускаем
            continue
        visited[v] = True
        total += w
        if parent != -1:
            mst.append((parent, v, w))
        for to, wt in adj[v]:
            if not visited[to]:
                heapq.heappush(heap, (wt, to, v))
    return (mst, total) if len(mst) == n - 1 else (None, None)

Обратите внимание на структурное сходство с Дейкстрой: та же куча, тот же цикл, та же ленивая очистка. Разница ровно в одном месте — в Дейкстре в кучу кладётся dist[v] + wt (накопленная длина пути), в Приме — просто wt (вес одного ребра). Отсюда, кстати, следует, что Прим устойчив к отрицательным весам, а Дейкстра — нет.

Варианты сложности Прима:

Практическое правило: разреженный граф — Крускал (проще, кэш-дружелюбнее, легко распараллелить сортировку), плотный граф или граф, заданный неявно метрикой (например, евклидовы точки) — Прим за O(V²), потому что там материализовать все V²/2 рёбер для сортировки — самоубийство по памяти.

Алгоритм Борувки — недооценённый третий

Исторически первый (Отакар Борувка, 1926, задача электрификации Моравии) и самый интересный для современного железа.

BORUVKA(V, E):
    T = ∅;  каждая вершина — своя компонента
    пока компонент > 1:
        для каждой компоненты C:                      # ← это делается параллельно
            найти минимальное ребро, выходящее из C
        добавить все найденные рёбра в T
        объединить компоненты
    вернуть T

Ключевое наблюдение: за одну фазу число компонент уменьшается минимум вдвое (каждая компонента с кем-то сливается, значит размер каждой новой ≥ 2 старых). Значит фаз O(log V), каждая — O(E), итого O(E log V).

Почему это важно сегодня: фазы Борувки эмбарасингли параллельны. Поиск минимального исходящего ребра для каждой компоненты — это чистый map-reduce. Отсюда Борувка живёт в GPU-библиотеках (cuGraph), в распределённых фреймворках и внутри гибридных алгоритмов. Karger–Klein–Tarjan (1995) комбинируют фазы Борувки с рандомизированной выборкой и получают MST за ожидаемое линейное время O(E) — см. Рандомизированные алгоритмы. Детерминированный рекорд — алгоритм Шазеля за O(E α(E, V)), но он практически нереализуем.

Про параллельные варианты — Параллельные и распределённые алгоритмы.

Тонкость Борувки: при равных весах алгоритм может «зациклиться» — две компоненты выберут друг друга через разные рёбра одинакового веса, и вместо дерева получится цикл. Лечение: тотальный порядок на рёбрах — сравнивать пары (вес, индекс ребра). Это ловушка, на которой спотыкаются почти все, кто пишет Борувку впервые.

Выбор алгоритма

Полезные производные задачи

Минимаксный (bottleneck) путь. Минимизировать максимальное ребро на пути u → v. Ответ — путь в MST. Доказательство: пусть в MST на пути есть ребро e веса W, а существует путь с максимумом < W. Удалим e из MST — граф распадётся на две части; альтернативный путь пересекает этот разрез ребром веса < W, значит cycle property запрещает e быть в MST. Противоречие. Практика: маршрутизация с максимальной пропускной способностью канала, задачи «Heaters», «Path with Minimum Effort».

Второе по весу остовное дерево. Перебрать все не-древесные рёбра (u, v, w): добавление создаёт цикл, надо выкинуть максимальное ребро на пути u→v в дереве. Ответ — min по всем рёбрам (MST − max_на_пути + w). Максимум на пути считается двоичными подъёмами (binary lifting) за O(log V) на запрос, итого O(E log V).

Число остовных деревьев. Теорема Кирхгофа (matrix-tree theorem): равно любому алгебраическому дополнению матрицы Лапласа L = D − A. Считается детерминантом за O(V³).

Задача Штейнера (соединить не все, а заданное подмножество терминалов, разрешив добавлять новые вершины) — NP-трудна. MST на терминалах даёт 2-приближение. Это классический пример того, как маленькое ослабление условия ломает полиномиальность.

Что MST НЕ делает. Он не минимизирует диаметр, не минимизирует расстояния между парами вершин и не даёт кратчайших путей. Путать MST и дерево кратчайших путей (Дейкстры) — очень частая ошибка: это разные деревья с разными целевыми функциями. MST минимизирует сумму рёбер, дерево Дейкстры — расстояния от корня.

Часть II. Максимальный поток

Постановка

Дана ориентированная сеть G = (V, E) с неотрицательными пропускными способностями c(u, v) ≥ 0, выделены исток s и сток t. Поток — функция f(u, v), удовлетворяющая:

1. ограничение пропускной способности: 0 ≤ f(u, v) ≤ c(u, v);
2. сохранение потока: для любой v ∉ {s, t} входящий поток равен исходящему.

Величина потока |f| — суммарный поток, выходящий из s. Нужно максимизировать |f|.

Аналогия с водопроводом рабочая, но она немного вредит: у воды нет «желания» распределяться оптимально, а алгоритм должен искать глобальный оптимум. Более честная интуиция — параллельная логистика: сколько грузовиков в час можно прогнать из склада в магазин по дорожной сети с ограничениями на каждой дороге.

Почему наивная жадность ломается и что такое остаточная сеть

Наивный алгоритм: ищем любой путь s → t со свободной ёмкостью, шлём по нему максимум, повторяем. Это неверно — ранний выбор пути может «заблокировать» лучшую конфигурацию.

Починка — гениально простая. Введём остаточную сеть G_f: для каждого ребра (u, v) с потоком f и ёмкостью c заводим

• прямое остаточное ребро u → v с ёмкостью c − f («сколько ещё влезет»),
• обратное остаточное ребро v → u с ёмкостью f («сколько можно отменить»).

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

Дополняющий путь (augmenting path) — любой путь s → t в остаточной сети с положительными ёмкостями. Теорема: поток максимален тогда и только тогда, когда в G_f нет дополняющего пути.

Теорема о максимальном потоке и минимальном разрезе

Это центральный результат всей темы (Форд и Фалкерсон, 1956; независимо Элиас–Файнстейн–Шеннон).

s–t разрез — разбиение V = S ⊔ T, где s ∈ S, t ∈ T. Его ёмкость — сумма ёмкостей рёбер, идущих из S в T (обратные не считаются).

max-flow = min-cut. Максимальная величина потока равна минимальной ёмкости s–t разреза.

Доказательство в три шага (стоит уметь воспроизвести — оно короткое и красивое):

1. Слабая двойственность. Для любого потока f и любого разреза (S, T): |f| ≤ c(S, T). Весь поток обязан пересечь разрез, а пропустить больше ёмкости нельзя.
2. Если нет дополняющего пути, поток максимален. Пусть S — множество вершин, достижимых из s в G_f. Тогда t ∉ S. Каждое ребро из S в T насыщено (иначе оно вело бы дальше), каждое ребро из T в S имеет нулевой поток (иначе было бы обратное остаточное ребро). Значит |f| = c(S, T) ровно.
3. Из (1) и (2): найденный поток достиг верхней границы, значит и поток максимален, и разрез минимален. ∎

Практический вывод, который часто забывают: после вычисления max flow минимальный разрез получается бесплатно — одним BFS по остаточной сети из истока. Это, а не сам поток, нужно в половине прикладных задач (сегментация изображений, надёжность сети, image matting).

Форд–Фалкерсон, Эдмондс–Карп, Диниц

Общая схема одна: «пока есть дополняющий путь — пусти по нему поток». Различие — как искать путь, и от этого драматически меняется сложность.

Форд–Фалкерсон с произвольным выбором пути имеет сложность O(E · |f*|) — зависит от значения потока, то есть псевдополиномиален. Классический контрпример: «ромб» с рёбрами ёмкости 10⁹ и перемычкой ёмкости 1; невезучий выбор пути даст 2·10⁹ итераций вместо двух. Хуже того, на иррациональных ёмкостях Форд–Фалкерсон может не завершиться вовще и сойтись к значению, меньшему оптимума (пример Цвика). Никогда не пишите FF с DFS в продакшн.

Эдмондс–Карп — то же самое, но путь ищется BFS, то есть кратчайший по числу рёбер. Ключевая лемма: расстояние dist(s, v) в остаточной сети монотонно не убывает, а каждое ребро может стать «узким местом» не более O(V) раз. Итого O(V·E) дополнений, каждое O(E) → O(V·E²). Уже полиномиально и не зависит от ёмкостей.

Диниц — то, что нужно писать в реальности. Идея: не искать пути по одному, а за одну фазу «выжимать» всё, что можно, из слоистой сети.

Две гарантии, дающие сложность:

• Длина кратчайшего пути s→t строго растёт после каждой фазы, значит фаз не больше V−1.
• Блокирующий поток в слоистой сети находится за O(V·E) благодаря указателям текущей дуги (it[v]): если из вершины по какой-то дуге пропихнуть не удалось, дуга больше в этой фазе не рассматривается — указатель не откатывается.

Итого O(V² · E). Более того:

• на единичных ёмкостях Диниц работает за O(E · √E);
• на двудольных графах с единичными ёмкостями — O(E · √V), что в точности совпадает с оценкой Хопкрофта–Карпа для паросочетаний (это, по сути, тот же алгоритм);
• на реальных «человеческих» графах Диниц обычно ведёт себя гораздо лучше оценки.

from collections import deque


class Dinic:
    """Максимальный поток алгоритмом Диница.
    Рёбра хранятся парами: рёбра 2k и 2k^1=2k+1 — прямое и обратное.
    Отсюда трюк eid ^ 1 — «парное ребро».
    Время: O(V² E) в общем случае, O(E √E) при единичных ёмкостях."""

    def __init__(self, n: int) -> None:
        self.n = n
        self.graph: list[list[int]] = [[] for _ in range(n)]  # список индексов рёбер
        self.edges: list[list[int]] = []                      # [куда, остаточная ёмкость]

    def add_edge(self, u: int, v: int, cap: int) -> int:
        eid = len(self.edges)
        self.graph[u].append(eid)
        self.edges.append([v, cap])
        self.graph[v].append(eid + 1)
        self.edges.append([u, 0])          # обратное ребро: изначально ёмкость 0
        return eid

    def _bfs(self, s: int, t: int) -> bool:
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for eid in self.graph[v]:
                to, cap = self.edges[eid]
                if cap > 0 and self.level[to] < 0:
                    self.level[to] = self.level[v] + 1
                    q.append(to)
        return self.level[t] >= 0

    def _dfs(self, v: int, t: int, pushed: int) -> int:
        if v == t or pushed == 0:
            return pushed
        # it[v] — указатель текущей дуги: не откатывается в пределах фазы
        while self.it[v] < len(self.graph[v]):
            eid = self.graph[v][self.it[v]]
            to = self.edges[eid][0]
            if self.level[to] == self.level[v] + 1 and self.edges[eid][1] > 0:
                tr = self._dfs(to, t, min(pushed, self.edges[eid][1]))
                if tr > 0:
                    self.edges[eid][1] -= tr
                    self.edges[eid ^ 1][1] += tr
                    return tr
            self.it[v] += 1
        return 0

    def max_flow(self, s: int, t: int) -> int:
        flow = 0
        while self._bfs(s, t):             # фаза: построили слоистую сеть
            self.it = [0] * self.n
            while True:                    # выжимаем блокирующий поток
                pushed = self._dfs(s, t, float("inf"))
                if pushed == 0:
                    break
                flow += pushed
        return flow

    def min_cut(self, s: int) -> list[bool]:
        """Вызывать ПОСЛЕ max_flow. Возвращает маску S — достижимые из s
        в остаточной сети. Рёбра из S в V\\S и есть минимальный разрез."""
        seen = [False] * self.n
        seen[s] = True
        q = deque([s])
        while q:
            v = q.popleft()
            for eid in self.graph[v]:
                to, cap = self.edges[eid]
                if cap > 0 and not seen[to]:
                    seen[to] = True
                    q.append(to)
        return seen

Про рекурсию в _dfs. На Python при глубоких сетях легко словить RecursionError. В проде либо поднимайте sys.setrecursionlimit, либо переписывайте DFS итеративно со стеком (см. Рекурсия). В C++/Go/Rust проблема обычно не возникает.

Push-relabel: другая парадигма

Диниц и родня работают с корректными потоками на каждом шаге. Push-relabel (Goldberg–Tarjan) работает с предпотоком (preflow): временно разрешает вершинам накапливать избыток, а потом «сливает» его обратно. Каждая вершина имеет высоту h(v), поток проталкивается только «вниз», застрявшая вершина поднимается.

На практике push-relabel с эвристиками (gap heuristic, global relabeling, highest-label selection) часто быстрее Диница на больших плотных сетях и лучше параллелизуется. Именно он лежит в основе промышленных реализаций: google/or-tools, LEMON, boost::graph::push_relabel_max_flow. Но написать его правильно с нуля заметно сложнее, поэтому дефолт для собственного кода — Диниц, а для серьёзных объёмов — готовая библиотека.

Часть III. Моделирование: где потоки живут на самом деле

Настоящая сила потоков — в сведениях. Ниже — набор приёмов, покрывающий большинство реальных случаев.

Двудольное паросочетание

Задача: n работников, m задач, известно кто что умеет; назначить максимум пар.

Сведение: исток s → каждый работник (ёмкость 1) → допустимые задачи (ёмкость 1) → сток t (ёмкость 1). Максимальный поток = максимальное паросочетание. Единичные ёмкости → Диниц работает за O(E √V).

Целочисленность здесь не случайна: теорема о целочисленности гласит, что если все ёмкости целые, то существует максимальный поток с целыми значениями на всех рёбрах, и все рассмотренные алгоритмы его и находят. Именно поэтому «поток 1 по ребру» осмысленно читается как «назначение сделано».

Бонусы, которые выпадают из min-cut:

• Теорема Кёнига: в двудольном графе максимальное паросочетание = минимальное вершинное покрытие. Само покрытие извлекается из минимального разреза.
• Максимальное независимое множество в двудольном графе = V − минимальное покрытие.

Выбор проектов (max closure) — самый недооценённый приём

Задача: есть проекты с прибылями p_i (могут быть отрицательными — это затраты) и зависимости «чтобы взять проект A, нужно взять B». Выбрать подмножество с максимальной суммарной прибылью.

Сведение: s → (проекты с p > 0, ёмкость p), (проекты с p < 0) → t с ёмкостью |p|, зависимости — рёбрами бесконечной ёмкости. Тогда

максимальная прибыль = сумма всех положительных p − минимальный разрез

Бесконечные рёбра гарантируют, что разрез никогда не «перережет» зависимость: если проект выбран, все его пререквизиты обязаны попасть в ту же сторону разреза. Гениально просто.

Эта же схема — project selection / closure problem — используется для:

• открытой добычи полезных ископаемых (какие блоки породы выгодно вынуть с учётом того, что вышележащие приходится убирать),
• выбора фич продукта с зависимостями,
• сегментации изображений (Boykov–Kolmogorov graph cuts): пиксели — вершины, стоимость метки — рёбра к s/t, штраф за разрыв между соседями — рёбра между пикселями. Реализация Бойкова–Колмогорова специально оптимизирована под сеточные графы: pami04.pdf.

Набор стандартных трюков моделирования

Поток минимальной стоимости (MCMF)

Обобщение: у каждого ребра есть ещё и стоимость за единицу потока. Нужно среди всех максимальных потоков (или потоков заданной величины) найти самый дешёвый. Это модель назначений: кто-кому-какой-ценой.

Алгоритм: тот же Форд–Фалкерсон, но дополняющий путь выбирается кратчайшим по стоимости. Ключевая теорема: если каждый раз дополнять по кратчайшему пути, промежуточные потоки остаются оптимальными для своей величины (successive shortest paths). Поскольку обратные рёбра имеют отрицательную стоимость, Дейкстра напрямую не годится — нужен Беллман–Форд/SPFA либо потенциалы Джонсона (см. Кратчайшие пути).

class MinCostFlow:
    """Successive shortest paths + SPFA (очередь Беллмана-Форда).
    Работает с отрицательными стоимостями обратных рёбер.
    Время: O(F · V · E) в худшем случае; с потенциалами Джонсона + Дейкстра — O(F · E log V)."""

    def __init__(self, n: int) -> None:
        self.n = n
        self.graph: list[list[int]] = [[] for _ in range(n)]
        self.edges: list[list[int]] = []      # [куда, остаточная ёмкость, стоимость]

    def add_edge(self, u: int, v: int, cap: int, cost: int) -> None:
        self.graph[u].append(len(self.edges))
        self.edges.append([v, cap, cost])
        self.graph[v].append(len(self.edges))
        self.edges.append([u, 0, -cost])      # отмена потока возвращает стоимость

    def flow(self, s: int, t: int, need: float = float("inf")) -> tuple[int, int]:
        INF = float("inf")
        total_flow = total_cost = 0
        while total_flow < need:
            dist = [INF] * self.n
            dist[s] = 0
            in_queue = [False] * self.n
            prev_edge = [-1] * self.n
            q = deque([s])
            in_queue[s] = True
            while q:                                   # SPFA
                v = q.popleft()
                in_queue[v] = False
                for eid in self.graph[v]:
                    to, cap, cost = self.edges[eid]
                    if cap > 0 and dist[v] + cost < dist[to]:
                        dist[to] = dist[v] + cost
                        prev_edge[to] = eid
                        if not in_queue[to]:
                            in_queue[to] = True
                            q.append(to)
            if dist[t] == INF:                         # сток недостижим — всё
                break
            push = need - total_flow                   # узкое место на найденном пути
            v = t
            while v != s:
                eid = prev_edge[v]
                push = min(push, self.edges[eid][1])
                v = self.edges[eid ^ 1][0]
            v = t
            while v != s:                              # применяем
                eid = prev_edge[v]
                self.edges[eid][1] -= push
                self.edges[eid ^ 1][1] += push
                v = self.edges[eid ^ 1][0]
            total_flow += push
            total_cost += push * dist[t]
        return total_flow, total_cost

Важно: если в исходном графе есть циклы отрицательной стоимости, successive shortest paths не применим напрямую — сначала нужно устранить их (cycle canceling или начальная циркуляция). На практике почти во всех прикладных моделях стоимости неотрицательны, и это не проблема.

Связь между MST и потоками: дерево Гомори–Ху

Красивый мост между двумя частями статьи. Для неориентированного графа существует дерево Гомори–Ху на тех же вершинах: для любой пары (u, v) минимальный u–v разрез в исходном графе равен минимальному ребру на пути u→v в этом дереве. То есть все C(n,2) минимальных разрезов кодируются деревом из n−1 рёбер, и строится оно за n−1 вызовов max-flow.

Обратите внимание на симметрию: MST кодирует минимаксные пути, дерево Гомори–Ху кодирует минимальные разрезы. Оба — сжатие квадратичной информации в дерево.

Глобальный минимальный разрез (без фиксированных s и t) можно получить и без потоков — алгоритмом Штёра–Вагнера за O(V·E + V² log V) или рандомизированным алгоритмом Каргера.

Типичные ошибки

1. Переполнение при INF. Классика: рёбра «бесконечной» ёмкости задают как INT_MAX, потом складывают — переполнение, отрицательные ёмкости, бесконечный цикл. Берите INF размером с сумму реальных ёмкостей плюс запас, а не максимум типа.
2. Забыли обратное ребро или создали его с ненулевой ёмкостью. Симптом: поток больше правильного ответа. В неориентированном графе обе ёмкости равны c — это другая ситуация, и путать её с ориентированной нельзя.
3. Ford–Fulkerson с DFS в проде. Работает на тестах, зависает на большом входе. Всегда BFS (Эдмондс–Карп) как минимум, лучше Диниц.
4. Указатель текущей дуги не сбрасывается между фазами — тогда Диниц просто теряет поток и выдаёт заниженный ответ. self.it = [0]*n должно быть внутри цикла по фазам.
5. Забыли, что min-cut — это рёбра из S в T, а не «все рёбра между S и T». Обратные не считаются, иначе ёмкость завышена.
6. MST на несвязном графе. Крускал молча вернёт лес. Проверяйте components == 1 явно, иначе получите «правдоподобный, но бессмысленный» ответ.
7. Борувка при равных весах без тотального порядка на рёбрах — циклы вместо дерева (см. выше).
8. Прим на графе с отрицательными весами — работает корректно (в отличие от Дейкстры), но люди на всякий случай «сдвигают веса», добавляя константу. Для MST это безопасно (все остовные деревья содержат ровно V−1 рёбер, сдвиг одинаково влияет на все), для кратчайших путей — нет. Не переносите привычку.
9. Ленивая куча в Приме растёт до O(E) — на очень плотных графах это память. Тогда используйте O(V²)-версию.
10. Вещественные ёмкости. Кроме проблемы завершения FF, накапливается ошибка округления, и min-cut «плавает». Масштабируйте до целых, если возможно.

Как это применяют в проде

Максимальный поток редко вызывается напрямую в бизнес-коде — но постоянно оказывается внутри чего-то большего:

• Планировщики и распределение ресурсов. Назначение задач на машины с ограничениями по CPU/памяти — это транспортная задача, частный случай min-cost flow. В Kubernetes и Borg реальные планировщики эвристические (важнее скорость и инкрементальность), но Firmament (исследовательский планировщик от Cambridge/Google) явно строит min-cost flow сеть и решает её на каждом цикле.
• Рекламные аукционы и матчинг. Распределение показов между рекламодателями с бюджетами — задача о потоке с ёмкостями-бюджетами. Онлайн-версии решаются приближённо, но LP-релаксация и её двойственная задача (те самые потенциалы) — прямой потомок теории потоков.
• Computer vision. Graph cuts для сегментации и стерео — де-факто стандарт до эры глубокого обучения, и до сих пор используется как post-processing (CRF поверх выхода нейросети).
• Baseball elimination — классический пример из Sedgewick: «может ли команда ещё выиграть чемпионат» решается max-flow. Тот же приём применим к любым турнирам и прогнозам.
• MST в сетях и кластеризации. Построение оверлейных топологий, spanning tree protocol (STP/RSTP) в Ethernet — правда, там дерево не минимальное по весу, а по стоимости пути к корню, но родство прямое. В ML — single-linkage кластеризация и HDBSCAN строятся ровно на MST (см. Машинное обучение).

Готовые библиотеки, а не свой код, если задача серьёзная:

• Google OR-Tools max flow — быстрый push-relabel, C++ с обёртками на Python/Java/C#.
• NetworkX flow algorithms — для прототипирования и анализа, включая minimum_cut и network_simplex.
• LEMON — C++, один из самых быстрых наборов для потоков и MCMF.
• SciPy: scipy.sparse.csgraph.minimum_spanning_tree и maximum_flow.

Когда потоки — неправильный инструмент. Если ограничения не выражаются линейно и целочисленно (например, «не более трёх задач подряд одному человеку»), сеть построить не получится, и надо идти в MILP-солвер (CBC, HiGHS, Gurobi) или в метаэвристики. Потоки — это очень быстрый частный случай линейного программирования; как только задача выходит за рамки этого частного случая, попытки «дожать» её потоком превращаются в грязный хак.

Мини-итог

• MST — это жадность, которой повезло со структурой. Cut property разрешает брать, cycle property разрешает выбрасывать; Крускал, Прим и Борувка — три расписания одних и тех же покрасок. Выбор между ними определяется плотностью графа и требованиями к параллелизму, а не «модой».
• MST даёт больше, чем сумму рёбер: минимаксные пути, single-linkage кластеризацию, 2-приближение метрического TSP.
• Потоки — это жадность, которую починили обратными рёбрами. Остаточная сеть — универсальный приём «сделать локальный выбор обратимым», и он переиспользуется далеко за пределами потоков.
• max-flow = min-cut — и разрез после вычисления потока достаётся одним BFS. Часто именно разрез, а не поток, и был нужен.
• Диниц — практический дефолт (O(V²E), O(E√V) на паросочетаниях); push-relabel — для больших плотных сетей и готовых библиотек.
• Главный навык — не реализация, а моделирование. Расщепление вершин, супер-исток, бесконечные рёбра для зависимостей, max closure — этот словарь превращает «странную задачу про бизнес» в 20 строк построения графа.

Источники

• CLRS, Introduction to Algorithms, 4-е изд. — гл. 21 (MST), гл. 24 (Maximum Flow). Каноническое изложение с полными доказательствами.
• R. Sedgewick, K. Wayne, Algorithms, 4th ed. — algs4: Minimum Spanning Trees и Maxflow. Лучшие иллюстрации и Java-код.
• S. Skiena, The Algorithm Design Manual — прикладной взгляд, «какую задачу чем сводить».
• Ahuja, Magnanti, Orlin, Network Flows: Theory, Algorithms, and Applications — библия потоков, если тема нужна всерьёз.
• cp-algorithms: Крускал, Прим, Диниц, MCMF.
• A. Schrijver, On the history of the transportation and maximum flow problems — PDF. Отличная историческая справка: задача возникла из анализа пропускной способности советской железнодорожной сети.
• Karger, Klein, Tarjan (1995), A randomized linear-time algorithm to find minimum spanning trees — ACM DL.
• Chen, Kyng, Liu, Peng, Probst Gutenberg, Sachdeva (2022), Maximum Flow and Minimum-Cost Flow in Almost-Linear Time — arXiv:2203.00671. Прорыв, снявший вопрос об асимптотике; практических реализаций пока нет.
• Boykov, Kolmogorov (2004), An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision — PDF.

Что дальше

Мы закончили с графами. Дальше — совершенно другой мир, где данные линейны, но структура прячется внутри самой последовательности символов: префикс-функции, автоматы и хеширование, позволяющие искать подстроки за линейное время.

Строковые алгоритмы: KMP, Z-функция, Ахо–Корасик, хеширование