我的算法书 - Dinic 最大流算法

一句话算法

Dinic 先用 BFS 把残量网络分层，再用 DFS 在分层图里一次推完尽可能多的流。

问题模型

给定一个有向网络：

每条边有容量；
源点 s 产生流量；
汇点 t 接收流量；
除 s 和 t 外，每个点满足流量守恒。

目标是求从 s 到 t 的最大流。

Dinic 和 Edmonds-Karp 解决的是同一个最大流问题，但 Dinic 不再每次只找一条增广路，而是在一张分层图里批量增广。

核心直觉

Edmonds-Karp 每轮 BFS 找一条最短增广路。问题是：一条一条找太慢。

Dinic 的改进是：

BFS 得到每个点距离源点的层数。
只允许流从第 k 层流向第 k+1 层。
在这张分层图上 DFS，把所有能推的最短增广路尽量推完。
当前分层图推不动后，重新 BFS 分层。

分层图像一个方向明确的水渠系统，DFS 只沿着层数增加的边走，减少无效搜索。

关键概念

残量网络

一条边剩余还能通过多少流量，叫残量容量。

每加入一条正向边，都要加入一条反向边。正向边被使用后，反向边容量增加，表示后续可以撤销这部分流量。

分层图

BFS 从源点出发，只走残量容量大于 0 的边。

若 level[v] = level[u] + 1，边 u -> v 就是当前分层图中的允许边。

当前弧优化

DFS 从点 u 尝试过一条边后，如果这条边已经没有可用价值，同一轮分层图里没必要再从头扫描。

所以每个点维护 current[u]，记录下一条应该尝试的边。

算法步骤

建图时，每条原边加入一条容量为 0 的反向边。
在残量网络上 BFS：
- 若汇点不可达，算法结束；
- 否则得到分层图。
将当前弧数组 current 初始化为 head。
从源点 DFS 增广：
- 只走 capacity > 0 且 level[v] = level[u] + 1 的边；
- 找到流量后修改正向边和反向边；
- 一轮 BFS 下反复 DFS，直到源点再也推不出流。
重新 BFS，继续下一轮。

算法证明

核心不变量：残量网络始终正确表示当前流量还能如何增加或撤销。

每次 DFS 沿允许边增广时：

正向边容量减少，表示使用了容量。
反向边容量增加，表示这部分流量允许被撤销。
流量仍满足容量限制和流量守恒。

BFS 分层只保留当前残量网络中的最短增广方向。DFS 把当前分层图中的可行增广尽量推完后，当前最短长度的增广路已经不存在。

当某次 BFS 无法到达汇点时，残量网络中不存在任何 s -> t 路径。此时源点可达集合与不可达集合之间没有剩余容量，形成一个割。根据最大流最小割定理，当前流就是最大流。

复杂度分析

设点数为 $V$ ，边数为 $E$ 。

一次 BFS： $O(E)$ 。
一轮分层图中的 DFS 在当前弧优化下会顺序扫描边。
Dinic 一般图最坏时间复杂度： $O(V^2E)$ 。
二分图匹配等特殊网络上有更好的复杂度表现。
空间复杂度： $O(V+E)$ 。

实际竞赛中，Dinic 是最常用的最大流模板之一，通常比 Edmonds-Karp 快很多。

代码实现

模板输入格式：

n m s t
u1 v1 c1
u2 v2 c2
...
um vm cm

输出最大流。

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

        #include <bits/stdc++.h>
using namespace std;

struct Dinic {
    struct Edge {
        int to;
        int next;
        long long capacity;
    };

    vector<Edge> edges;
    vector<int> head;
    vector<int> level;
    vector<int> current;
    int node_count = 0;

    Dinic(int n = 0, int max_edges = 0) {
        init(n, max_edges);
    }

    void init(int n, int max_edges = 0) {
        node_count = n;
        edges.clear();
        edges.reserve(max_edges * 2 + 5);
        head.assign(n + 1, -1);
        level.resize(n + 1);
        current.resize(n + 1);
    }

    void add_edge(int u, int v, long long capacity) {
        edges.push_back({v, head[u], capacity});
        head[u] = (int)edges.size() - 1;
        edges.push_back({u, head[v], 0});
        head[v] = (int)edges.size() - 1;
    }

    bool bfs(int source, int sink) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[source] = 0;
        q.push(source);

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

            for (int i = head[u]; i != -1; i = edges[i].next) {
                int v = edges[i].to;
                if (edges[i].capacity <= 0 || level[v] != -1) continue;
                level[v] = level[u] + 1;
                q.push(v);
            }
        }

        return level[sink] != -1;
    }

    long long dfs(int u, int sink, long long limit) {
        if (u == sink || limit == 0) return limit;

        long long flow = 0;
        for (int &i = current[u]; i != -1; i = edges[i].next) {
            int v = edges[i].to;
            if (edges[i].capacity <= 0 || level[v] != level[u] + 1) continue;

            long long pushed = dfs(v, sink, min(limit, edges[i].capacity));
            if (pushed == 0) continue;

            edges[i].capacity -= pushed;
            edges[i ^ 1].capacity += pushed;
            flow += pushed;
            limit -= pushed;
            if (limit == 0) break;
        }

        if (flow == 0) level[u] = -1;
        return flow;
    }

    long long max_flow(int source, int sink) {
        long long answer = 0;
        while (bfs(source, sink)) {
            current = head;
            while (true) {
                long long flow = dfs(source, sink, numeric_limits<long long>::max());
                if (flow == 0) break;
                answer += flow;
            }
        }
        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, source, sink;
    cin >> n >> m >> source >> sink;

    Dinic dinic(n, m);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long capacity;
        cin >> u >> v >> capacity;
        dinic.add_edge(u, v, capacity);
    }

    cout << dinic.max_flow(source, sink) << '\n';
    return 0;
}

测试用例

输入：

输出：

这组数据中，源点 1 的总出边容量为 5，并且这些流量都能到达汇点 4，所以最大流为 5。

应用分类详解

Dinic 的本质是高效求最大流。只要题目能被建成“容量网络”，就可以考虑 Dinic。

一、最大流模板与运输问题

典型模式： 有源点、汇点、通道容量，问最多能输送多少。

识别信号： 出现“容量”“流量”“最多运输”“管道”“网络”。

核心建模： 点表示位置或状态，边容量表示最大可通过量。

应用场景	经典题目	核心思路
最大流模板	luogu-P3376	直接按容量建图
排水沟模型	poj-1273	管道容量就是边容量

二、二分图最大匹配

典型模式： 左右两类对象配对，每个对象最多匹配一次。

识别信号： 出现“匹配”“分配”“每个只能选一个”。

核心建模： S -> 左部 容量为 1，可匹配关系连 左部 -> 右部，右部 -> T 容量为 1。

应用场景	经典题目	核心思路
二分图匹配	luogu-P3386	单位容量网络最大流
食物与饮料分配	poj-3281	拆点限制每头牛只能被选一次

三、带点容量限制的问题

典型模式： 不只是边有容量，点也有通过次数限制。

识别信号： 出现“每个点最多使用一次”“每个人最多承担一个任务”。

核心建模： 把点 x 拆成 x_in -> x_out，这条边容量就是点容量。

四、最小割模型

典型模式： 要在若干代价中选择切断一些关系，使两个集合分开。

识别信号： 出现“最小代价切断”“二选一收益/损失”“闭合子图”。

核心建模： 最大流等于最小割，求完最大流后从残量网络可达性可以恢复割。

经典例题

1. luogu-P3376

最大流模板题。重点练习反向边、分层图和当前弧。

2. luogu-P3386

二分图最大匹配。可以用 Dinic 建单位容量网络，也可以使用匈牙利算法。

3. poj-3281

Dining。经典拆点建图题：食物到牛，牛拆点后到饮料，保证每头牛只被选一次。

参考

本书 Edmonds-Karp 章节：graph/netflow/ek.md