网络流（Dinic）提高组

💡 核心思想

网络流是在有向图中求最大流或最小费用流的算法族。Dinic 算法是其中效率较高的算法：通过 BFS 构建分层图（按到源点的距离分层），然后用 DFS 在分层图上寻找阻塞流。关键技巧是当前弧优化——记录每个点上次搜索到哪条边，避免重复遍历。时间复杂度 O(n²m)，在单位容量网络中为 O(m√n)。

🎯 直觉理解

想象你在城市的供水系统中，每条水管有一个容量限制。你想知道从水厂到居民区的最大供水量是多少。Dinic 算法先用水位计（BFS）给每个节点标上距离水厂的层数，然后让水从高层流向低层（DFS），直到某一层的水管全部饱和（阻塞流）。然后重新分层，继续输水。

📝 算法流程

1. 建图：每条边存储容量和反向边（用于残量网络）
2. BFS 分层：从源点出发，给每个节点标上距离层次
3. 如果汇点无法到达，算法结束
4. DFS 找阻塞流：只沿层次递增的边发送流量
5. 当前弧优化：记录每个节点上次遍历到的边，下次从这里继续
6. 重复 BFS + DFS 直到无增广路

$$\text{最大流} = \sum \text{从源点发出的流量} = \sum \text{到达汇点的流量}$$

$$\text{最小割} = \text{最大流} \quad \text{（最大流最小割定理）}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
using ll = long long;
const ll INF = 1e18;

struct Edge {
    int to, rev;
    ll cap;
};

struct Dinic {
    int n, s, t;
    vector> g;
    vector level, iter;
    
    Dinic(int n) : n(n), g(n), level(n), iter(n) {}
    
    void addEdge(int from, int to, ll cap) {
        g[from].push_back({to, (int)g[to].size(), cap});
        g[to].push_back({from, (int)g[from].size() - 1, 0});
    }
    
    bool bfs() {
        fill(level.begin(), level.end(), -1);
        queue q;
        level[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : g[u])
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
        }
        return level[t] >= 0;
    }
    
    ll dfs(int u, ll f) {
        if (u == t) return f;
        for (int& i = iter[u]; i < g[u].size(); i++) {
            Edge& e = g[u][i];
            if (e.cap > 0 && level[u] < level[e.to]) {
                ll d = dfs(e.to, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    ll maxFlow(int s, int t) {
        this->s = s; this->t = t;
        ll flow = 0;
        while (bfs()) {
            fill(iter.begin(), iter.end(), 0);
            ll f;
            while ((f = dfs(s, INF)) > 0) flow += f;
        }
        return flow;
    }
};

int main() {
    Dinic dinic(6);
    dinic.addEdge(0, 1, 16);
    dinic.addEdge(0, 2, 13);
    dinic.addEdge(1, 2, 10);
    dinic.addEdge(1, 3, 12);
    dinic.addEdge(2, 4, 14);
    dinic.addEdge(3, 2, 9);
    dinic.addEdge(3, 5, 20);
    dinic.addEdge(4, 3, 7);
    dinic.addEdge(4, 5, 4);
    cout << dinic.maxFlow(0, 5) << endl; // 23
    return 0;
}

⚠️ 常见坑点

📚 相关题目