网络流与最大流 (Dinic 算法)¶

在容量网络中，最大流问题 (Maximum Flow Problem) 旨在求解从源点 \(S\)（Source）出发，流经有向网络各条具有容量限制的边，最终到达汇点 \(T\)（Sink）的最大总流量。

根据 最大流最小割定理 (Max-Flow Min-Cut Theorem)，网络的最大流值严格等于该网络将 \(S\) 与 \(T\) 隔开的最小割容量。

Dinic 算法原理¶

Dinic 算法是算法竞赛中最通用且实战效率最高的最大流算法。它结合了 BFS 分层图 (Level Graph) 与 DFS 寻找多路增广阻塞流 (Blocking Flow)：

BFS 构建分层图：从源点 \(S\) 开始 BFS，计算每个节点的深度编号 \(level[u]\)。增广时只允许沿 \(level[v] = level[u] + 1\) 的边进行推进，彻底消除无用环路。若无法到达 \(T\)，算法终止。
DFS 寻找阻塞流：在分层图上利用 DFS 同时推进多条增广路径。
当前弧优化 (Current Arc Optimization)：维护指针 cur[u]，记录节点 \(u\) 当前推进到的出边。一旦某条边容量已满或无法继续推流，下一次访问直接从 cur[u] 开始，避免重复遍历废边。

复杂度表现¶

一般网络：理论最坏 \(\mathcal{O}(V^2 E)\)，实战由于分层图剪枝与当前弧优化，常数极小，可轻松跑过 \(V \le 10^4, E \le 10^5\) 的网络。
单位容量网络（如二分图匹配）：理论时间复杂度自动优化至 \(\mathcal{O}(E \sqrt{V})\)。

完整 C++ 模版实现¶

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

template <typename T = long long>
struct Dinic {
    struct Edge {
        int to;
        T cap;
        T flow;
        int rev; // 反向边在邻接表中的下标
    };

    int n, s, t;
    std::vector<std::vector<Edge>> adj;
    std::vector<int> level;
    std::vector<int> cur; // 当前弧指针

    static constexpr T INF = std::numeric_limits<T>::max() / 2;

    Dinic(int n, int s, int t) : n(n), s(s), t(t), adj(n), level(n), cur(n) {}

    // 添加有向边 (单向容量 cap; 若为无向图, 反向边容量亦为 cap)
    void add_edge(int from, int to, T cap) {
        adj[from].push_back({to, cap, 0, (int)adj[to].size()});
        adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1});
    }

    // BFS 建立分层图
    bool bfs() {
        std::fill(level.begin(), level.end(), -1);
        std::queue<int> q;
        level[s] = 0;
        q.push(s);

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

            for (const auto &e : adj[u]) {
                if (e.cap - e.flow > 0 && level[e.to] == -1) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1; // 能否到达汇点
    }

    // DFS 多路增广
    T dfs(int u, T pushed) {
        if (pushed == 0 || u == t) return pushed;

        for (int &cid = cur[u]; cid < (int)adj[u].size(); ++cid) {
            auto &e = adj[u][cid];
            int v = e.to;

            if (level[v] != level[u] + 1 || e.cap - e.flow == 0) continue;

            T tr = dfs(v, std::min(pushed, e.cap - e.flow));
            if (tr == 0) continue;

            e.flow += tr;
            adj[v][e.rev].flow -= tr; // 反向边减退残量
            return tr;
        }
        return 0;
    }

    T max_flow() {
        T flow = 0;
        while (bfs()) {
            std::fill(cur.begin(), cur.end(), 0); // 重置当前弧
            while (T pushed = dfs(s, INF)) {
                flow += pushed;
            }
        }
        return flow;
    }

    // 求解最小割割边集: 返回所有满流且两端分别属于 S 集和 T 集的边
    std::vector<std::pair<int, int>> min_cut() {
        std::vector<bool> in_s(n, false);
        std::queue<int> q;
        q.push(s);
        in_s[s] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (const auto &e : adj[u]) {
                if (e.cap - e.flow > 0 && !in_s[e.to]) {
                    in_s[e.to] = true;
                    q.push(e.to);
                }
            }
        }

        std::vector<std::pair<int, int>> cut_edges;
        for (int u = 0; u < n; ++u) {
            if (in_s[u]) {
                for (const auto &e : adj[u]) {
                    if (!in_s[e.to] && e.cap > 0) {
                        cut_edges.push_back({u, e.to});
                    }
                }
            }
        }
        return cut_edges;
    }
};

[!TIP] 对于每条边同时带有单位流量费用的网络流问题，请参阅最小费用最大流 (MCMF)。