过程

整体来说，Dinic 是不断 BFS 分层 和 DFS 增广 的过程。

BFS 分层

每个点的 层数 即为它到源点的最短距离，源点的 层数 为 \(0\)。

通过它，我们可以发现：

  1. 当汇点没有 层数 时，算法结束。
  2. 当每次搜索只搜比当前点 层数 多一的点，我们找到的肯定是最短的增广路。

DFS 增广

\(S\) 指源点，\(T\) 指汇点，\(c_i\) 指边 \(i\) 的剩余容量。

运用分层，我们可以轻易的找到最短增广路。

从起点开始，每次往下进行搜索，只搜比当前 层数 多一的点，当搜到 \(T\) 点，结束 DFS ，继续 BFS 分层。

优化

多路增广

该优化可让你一次搜到多条增广路。

当你从某个点回退到上一个点时，若该点还有剩余流量，那我们就考虑对其再进行 DFS。

当前弧优化

该优化可帮你避免不必要的搜索。

我们知道，当一条边剩余容量为 \(0\) 时，他就没有用了。

这时，我们可以考虑避免对这些边的搜索，把头指针指向下一条边就可以了。

同时，对于一次 DFS，它搜过的边不会再搜第二次，我们运用这个更新指针数组。

BFS 要更新指针数组。

时间复杂度：\(O(n^2m)\)，该复杂度是理论上限，一般会更小。

特殊情况

这里只给出结论，证明看 OI-Wiki。

若图中所有边容量为 \(1\)，Dinic 的复杂度为 \(\textstyle O(m\min\{m^{\frac{1}{2}},n^{\frac{2}{3}}\})\)。

若在图中所有边容量为 \(1\) 的基础上，除源汇点外每个结点 \(u\) 都满足出度为 \(1\) 或入度为 \(1\)，复杂度为 \(O(mn^{\frac{1}{2}})\)。

代码

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
#include <bits/stdc++.h>
using namespace std;

constexpr int N = 205, M = 5005;

using ll = long long;

constexpr ll LLINF = 1e18;

struct Graph {
    struct Edge {
        int v, nt;
        ll c;
    } e[M << 1];
    int hd[N], tot = 1;
    void add(int u, int v, ll c) { e[++tot] = {v, hd[u], c}, hd[u] = tot; }
    void uadd(int u, int v, ll c) { add(u, v, c), add(v, u, 0); }
} g;

int n, m;

namespace Dinic {
int S, T;
bool vis[N];
int dep[N], cur[N];
bool bfs() {
    queue<int> q;

    fill(vis, vis + n + 1, 0);

    q.push(S);
    dep[S] = 0, vis[S] = 1, cur[S] = g.hd[S];

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = g.hd[u]; i; i = g.e[i].nt) {
            int v = g.e[i].v;
            if (!vis[v] && g.e[i].c) {
                dep[v] = dep[u] + 1, cur[v] = g.hd[v]; // 注意还原 cur
                vis[v] = 1;
                q.push(v);
            }
        }
    }

    return vis[T];
}

ll dfs(int u, ll f) {
    if (u == T || f == 0) return f;

    ll res = 0;

    for (int i = cur[u]; i; i = g.e[i].nt) {
        int v = g.e[i].v;
        cur[u] = i; // 当前弧优化
        if (dep[v] == dep[u] + 1 && g.e[i].c) {
            ll t = dfs(v, min(f, g.e[i].c));
            if (t) {
                g.e[i].c -= t, g.e[i ^ 1].c += t;
                res += t, f -= t;
                if (!f) break;
            }
        }
    }

    return res;
}

ll flow() {
    ll flow = 0;
    while (bfs()) flow += dfs(S, LLINF);
    return flow;
}
} // namespace Dinic

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

    cin >> n >> m >> Dinic::S >> Dinic::T;

    for (int i = 1, u, v; i <= m; i++) {
        ll c;
        cin >> u >> v >> c;
        g.uadd(u, v, c);
    }

    cout << Dinic::flow() << endl;

    return 0;
}

参考：oi-wiki