Skip to content

🌊 Потоци и Срязове: От Начинаещи до Експерти

Потоците в мрежи (Network Flows) са един от най-мощните инструменти в алгоритмичното програмиране. Те моделират широк спектър от проблеми: от транспорт на стоки и маршрутизация на данни, до разпределяне на задачи и сегментация на изображения.

1. Максимален Поток (Maximum Flow)

1.1. Дефиниция

Нека имаме ориентиран граф \(G = (V, E)\), където всяко ребро \((u, v)\) има капацитет \(c(u, v) \ge 0\). Имаме два специални върха: * Източник (Source, \(S\)): Върхът, от който потокът извира. * Отток (Sink, \(T\)): Върхът, където потокът се влива.

Поток е функция \(f(u, v)\), която удовлетворява две условия: 1. Ограничение на капацитета: \(0 \le f(u, v) \le c(u, v)\). 2. Запазване на потока: За всеки връх \(v \in V \setminus \{S, T\}\), сумата на влизащия поток е равна на сумата на излизащия. \(\sum_{u} f(u, v) = \sum_{w} f(v, w)\)

Целта е да максимизираме общия поток, излизащ от \(S\) (който е равен на влизащия в \(T\)).

1.2. Метод на Форд-Фулкерсън (Ford-Fulkerson)

Основната идея е итеративно увеличаване на потока. 1. Започваме с \(f(u, v) = 0\) за всички ребра. 2. Търсим път от \(S\) до \(T\) в остатъчния граф (Residual Graph). Остатъчният капацитет на ребро е \(c_f(u, v) = c(u, v) - f(u, v)\). * Важно: Ако изпратим поток по \((u, v)\), добавяме "обратно ребро" \((v, u)\) с капацитет, равен на потока. Това ни позволява да "отменим" лоши решения по-късно. 3. Ако намерим такъв път (наречен Augmenting Path), увеличаваме потока по него с "тясното място" (минималния остатъчен капацитет по пътя). 4. Повтаряме, докато не можем да достигнем \(T\) от \(S\).

1.3. Алгоритъм на Едмъндс-Карп (Edmonds-Karp)

Това е конкретна имплементация на Форд-Фулкерсън, която използва BFS за намиране на най-краткия (като брой ребра) увеличаващ път. * Сложност: \(O(V E^2)\). * Подходящ за графи с до 500-1000 върха.

1.4. Алгоритъм на Диник (Dinic's Algorithm)

Стандартът за състезания. Той е много по-бърз от Едмъндс-Карп. * Идея: Вместо да пускаме BFS за всеки отделен път, Диник използва BFS, за да построи Level Graph (граф, съдържащ само ребра, водещи към по-далечен от \(S\) връх). * След това пускаме DFS многократно върху Level Graph-а, за да изпратим "блокиращ поток" (няколко пътя едновременно). * Сложност: \(O(V^2 E)\) в общия случай. * За мрежи с единични капацитети (напр. паросучетания): \(O(E \sqrt{V})\).

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

using namespace std;

const long long INF = 1e18;

struct Edge {
    int v;
    long long cap, flow;
    int rev; // индекс на обратното ребро в adj[v]
};

struct Dinic {
    int n;
    vector<vector<Edge>> adj;
    vector<int> level; // разстояние от S (BFS)
    vector<int> ptr;   // текущ индекс в adj за DFS (оптимизация)

    Dinic(int n) : n(n), adj(n), level(n), ptr(n) {}

    void add_edge(int u, int v, long long cap) {
        Edge a = {v, cap, 0, (int)adj[v].size()};
        Edge b = {u, 0, 0, (int)adj[u].size()}; // Обратно ребро с 0 капацитет
        adj[u].push_back(a);
        adj[v].push_back(b);
    }

    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        level[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto& e : adj[u]) {
                if (e.cap - e.flow > 0 && level[e.v] == -1) {
                    level[e.v] = level[u] + 1;
                    q.push(e.v);
                }
            }
        }
        return level[t] != -1;
    }

    long long dfs(int u, int t, long long pushed) {
        if (pushed == 0 || u == t) return pushed;
        for (int& cid = ptr[u]; cid < adj[u].size(); ++cid) {
            auto& e = adj[u][cid];
            if (level[u] + 1 != level[e.v] || e.cap - e.flow == 0) continue;
            long long tr = dfs(e.v, t, min(pushed, e.cap - e.flow));
            if (tr == 0) continue;
            e.flow += tr;
            adj[e.v][e.rev].flow -= tr;
            return tr;
        }
        return 0;
    }

    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while (long long pushed = dfs(s, t, INF)) {
                flow += pushed;
            }
        }
        return flow;
    }
};

2. Теорема за Максимален Поток и Минимален Срез (Max-Flow Min-Cut)

Един s-t срез (cut) е разделяне на върховете на две множества: \(A\) (съдържащо \(S\)) и \(B\) (съдържащо \(T\)). Капацитетът на среза е сумата от капацитетите на ребрата, отиващи от \(A\) към \(B\).

Теорема: Стойността на максималния поток е равна на капацитета на минималния срез.

Приложение: Избор на проекти (Project Selection Problem)

Имаме набор от проекти (носят печалба) и набор от инструменти/ресурси (струват пари). Всеки проект зависи от определени инструменти. Искаме да изберем проекти и инструменти, така че печалбата минус разходите да е максимална.

Решение с Min-Cut: 1. Създаваме източник \(S\) и свързваме \(S\) към всички проекти с капацитет = печалбата. 2. Създаваме отток \(T\) и свързваме всички инструменти към \(T\) с капацитет = цената. 3. Ако проект \(P\) изисква инструмент \(I\), добавяме ребро \(P \to I\) с капацитет \(\infty\). 4. Минималният срез в този граф представлява минималната загуба (нереализирана печалба + платени разходи). 5. Отговор = (Сума на всички възможни печалби) - Max Flow.

3. Паросучетания в Двуделен Граф (Bipartite Matching)

Задачата за намиране на максимален брой двойки в двуделен граф може директно да се реши с Максимален Поток. 1. Добавяме \(S\) и \(T\). 2. Свързваме \(S\) към всички върхове от лявата част с капацитет 1. 3. Свързваме всички върхове от дясната част към \(T\) с капацитет 1. 4. Всички съществуващи ребра насочваме от ляво на дясно с капацитет 1 (или \(\infty\)). 5. Max Flow = Max Matching.

С Диник това работи за \(O(E \sqrt{V})\), което е еквивалентно на специализирания алгоритъм на Хопкрофт-Карп (Hopcroft-Karp).

4. Потоци с Изисквания (Flows with Demands)

Понякога ребрата имат не само капацитет \(C_{max}\), но и долна граница \(L_{min}\) (т.е. задължително трябва да мине поне толкова поток).

4.1. Допустима циркулация

За да решим това: 1. За всяко ребро \((u, v)\) с граници \([L, R]\), заменяме го с ребро с капацитет \(R - L\). 2. Създаваме масив balance за всеки връх. За всяко ребро \((u, v)\) с долна граница \(L\), "взимаме" \(L\) от \(u\) (balance[u] -= L) и го "даваме" на \(v\) (balance[v] += L). 3. Създаваме нови супер-източник \(SS\) и супер-отток \(TT\). * Ако balance[v] > 0, добавяме ребро \(SS \to v\) с капацитет balance[v]. * Ако balance[v] < 0, добавяме ребро \(v \to TT\) с капацитет -balance[v]. 4. Пускаме Max Flow от \(SS\) до \(TT\). Ако всички ребра, излизащи от \(SS\), са наситени (flow == capacity), то допустима циркулация съществува.

5. Min-Cost Max-Flow

Ако всяко ребро има и "цена" (cost) за единица поток, задачата става по-сложна. Търсим максимален поток с минимална обща цена. Това обикновено се решава чрез модификация на Едмъндс-Карп, където вместо BFS използваме SPFA (Shortest Path Faster Algorithm) или Dijkstra с потенциали (за да се справим с отрицателни ръбове), за да намираме най-евтиния път в остатъчния граф.

6. Задачи за упражнение

  1. SPOJ FASTFLOW: Тест за бързината на вашия Dinic.
  2. CSES Download Speed: Класически Max Flow.
  3. CSES Police Chase: Намиране на ребрата на Min-Cut.
  4. Codeforces 1082G: Petya and Graph (Project Selection).
  5. UVa 10330: Power Transmission (Потоци с капацитети на върховете - разделяме върха на \(v_{in}\) и \(v_{out}\)).

Успех с потоците! Веднъж щом разберете как да моделирате задачата като граф, решението често е само един шаблон на Диник.