Потоки в сетях

Максимальный поток: теорема о разрезе, алгоритм Эдмондса-Карпа и приложения к паросочетаниям.

Сеть — ориентированный граф, где у каждого ребра есть пропускная способность. Максимальный поток — сколько «жидкости» можно прогнать из истока s в сток t. Фундаментальная теорема (Форда-Фалкерсона): максимальный поток равен минимальному разрезу — минимальной суммарной пропускной способности рёбер, удаление которых отделяет s от t. Поэтому потоками решаются задачи и про «сколько прогнать», и про «что перерезать». Алгоритм Эдмондса-Карпа: пока существует путь из s в t с положительными остаточными пропускными способностями (ищем его BFS), пускаем по нему поток и обновляем ОСТАТОЧНУЮ сеть: прямые рёбра уменьшаем, обратные увеличиваем. Обратные рёбра — ключ: они позволяют «передумать» и перенаправить уже пущенный поток.

Попробуйте сами — код можно менять

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const long long INF = 1e18;
int n, m;
std::vector<std::vector<long long>> cap;
std::vector<std::vector<int>> g;

long long bfs(int s, int t, std::vector<int> &parent) {
    std::fill(parent.begin(), parent.end(), -1);
    parent[s] = s;
    std::queue<std::pair<int, long long>> q;
    q.push({s, INF});

while (!q.empty()) {
        auto [v, flow] = q.front();
        q.pop();
        for (int to : g[v]) {
            if (parent[to] == -1 && cap[v][to] > 0) {
                parent[to] = v;
                long long nf = std::min(flow, cap[v][to]);
                if (to == t) return nf;
                q.push({to, nf});
            }
        }
    }
    return 0;
}

int main() {
    std::cin >> n >> m;
    cap.assign(n + 1, std::vector<long long>(n + 1, 0));
    g.assign(n + 1, {});

for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;
        if (cap[a][b] == 0 && cap[b][a] == 0) {
            g[a].push_back(b);
            g[b].push_back(a); // обратное ребро для остаточной сети
        }
        cap[a][b] += c;
    }

long long flow = 0, add;
    std::vector<int> parent(n + 1);
    while ((add = bfs(1, n, parent)) > 0) {
        flow += add;
        int v = n;
        while (v != 1) {
            int p = parent[v];
            cap[p][v] -= add;
            cap[v][p] += add;
            v = p;
        }
    }
    std::cout << "Максимальный поток: " << flow << "\n";
    return 0;
}

Входные данные (пример — можно менять)

Эдмондс-Карп, исток 1, сток n. Введите: 4 5, затем «a b пропускная»: 1 2 3, 1 3 2, 2 3 1, 2 4 2, 3 4 3

На примере максимальный поток равен 5: 2 единицы по пути 1→2→4, 2 по 1→3→4 и ещё 1 по 1→2→3→4. Сложность Эдмондса-Карпа — O(V·E²); для плотных задач существует более быстрый алгоритм Диница. Главное практическое применение — двудольные паросочетания: максимальное число пар «студент-проект», где каждый в одной паре. Стройте сеть: исток → студенты (пропускная 1) → допустимые проекты (пропускная 1) → сток. Максимальный поток = максимальное паросочетание.

Задание: смоделируйте на бумаге задачу «3 работника, 3 задачи, кто какую умеет» как сеть и прогоните через программу выше (пронумеруйте: 1 — исток, 2-4 — работники, 5-7 — задачи, 8 — сток). Отметьте урок пройденным.