Алгоритм Диница

Код

class Graph {
    struct Edge {
        int a, b, capacity, flow = 0;

        Edge(int a, int b, int capacity) :
            a(a), b(b), capacity(capacity) {}

        int other(int v) const {
            return v == b ? a : b;
        }

        int capacityTo(int v) const {
            return v == b ? capacity - flow : flow;
        }

        void addFlowTo(int v, int deltaFlow) {
            flow += (v == b ? deltaFlow : -deltaFlow);
        }
    };

    vector<Edge> edges;
    vector<vector<int>> graph;
    vector<int> dist, edgeTo, index;

    bool hasPath(int start, int finish) {
        dist.assign(graph.size(), 1e9);
        edgeTo.assign(graph.size(), -1);
        index.assign(graph.size(), 0);
        queue<int> q;

        dist[start] = 0;
        q.push(start);

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (int edgeIndex : graph[v]) {
                int to = edges[edgeIndex].other(v);
                if (dist[to] > dist[v] + 1 && edges[edgeIndex].capacityTo(to)) {
                    dist[to] = dist[v] + 1;
                    q.push(to);
                }
            }
        }

        return dist[finish] != 1e9;
    }

    bool dfs(int v, int finish) {
        if (v == finish)
            return 1;

        for (; index[v] < graph[v].size(); index[v]++) {
            int edgeIndex = graph[v][index[v]], to = edges[edgeIndex].other(v);
            if (dist[to] == dist[v] + 1 && edges[edgeIndex].capacityTo(to) && dfs(to, finish)) {
                edgeTo[to] = edgeIndex;
                return 1;
            }
        }

        return 0;
    }

    int getMinCapacity(int start, int finish) {
        int minCapacity = 1e9;
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
            minCapacity = min(minCapacity, edges[edgeTo[v]].capacityTo(v));
        return minCapacity;
    }

    void addFlow(int start, int finish, int deltaFlow) {
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
            edges[edgeTo[v]].addFlowTo(v, deltaFlow);
    }

public:
    Graph(int vertexCount) : graph(vertexCount) {}

    void addEdge(int from, int to, int capacity) {
        edges.push_back(Edge(from, to, capacity));
        graph[from].push_back(edges.size() - 1);
        graph[to].push_back(edges.size() - 1);
    }

    long long maxFlow(int start, int finish) {
        long long flow = 0;
        while (hasPath(start, finish)) {
            while (dfs(start, finish)) {
                int deltaFlow = getMinCapacity(start, finish);
                addFlow(start, finish, deltaFlow);
                flow += deltaFlow;
            }
        }
        return flow;
    }
};

Сложность

• Одна фаза стоит O(VE):

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

Всего в рамках одной фазы мы можем найти не более O(E) увеличивающих путей.

Все DFSы в рамках одной фазы работают суммарно за O(VE), а не за O((V + E) × E), так как мы не возвращаемся к пройденным ранее индексам.

На обновление потока вдоль каждого найденного пути нужно O(V) времени.

• Всего будет не более O(V) фаз:

После каждой фазы расстояние до стока строго увеличивается, так как мы насыщаем потоком хотя бы одно ребро на каждом кратчайшем пути.

С другой стороны, расстояние до стока не может превышать (V - 1).

Таким образом, общая сложность — O(V^2 × E).

Ссылки

Теория:

• e-maxx.ru — Алгоритм Диница нахождения максимального потока
• cp-algorithms.com — Maximum flow — Dinic's algorithm
• neerc.ifmo.ru/wiki — Схема алгоритма Диница
• wiki.algocode.ru — Алгоритм Диница
• codeforces.com — My way of understanding Dinic's algorithm
• codeforces.com — Worst-Case Graphs for Maximum Flow Algorithms
• usaco.guide — Dinic's Algorithm

Демонстрация:

• visualgo.net — Network Flow

Код:

• indy256/codelibrary/cpp/graphs/flows/max_flow_dinic.h
• ADJA/algos/Graphs/Dinic.cpp

Задачи:

• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 9