最小割就是最大流，（求完了之后的残留网络就是最小割）

最小割的求解方法

在 Dinic 算法中，求完最大流后，残留网络中不再存在从源点到汇点的增广路径。此时，我们可以通过一次 BFS，从源点出发遍历残留网络，标记所有仍可到达的顶点。代码中的 minCut() 函数正是利用最后一次 BFS 计算的结果：

cpp

复制编辑

std::vector<bool> minCut() { std::vector<bool> c(n); for (int i = 0; i < n; i++) { c[i] = (h[i] != -1); } return c; }

这里返回的布尔数组 c 表示每个顶点是否在源点 s 的可达集合 S 中。根据最大流最小割定理，从 S 到 T（不可达部分）的边就是最小割边。虽然函数本身只返回了 S 集合的信息，但你可以通过扫描所有边，找出那些一端在 S（c[u] == true）而另一端在 T（c[v] == false）的边，从而得到具体的割边。

dep 数组的作用

  • 层次标号：在 Dinic 算法中，h 数组用于存储每个顶点在残留网络中距离源点 s 的层次（或者称“高度”）。在 BFS 过程中，所有顶点初始值都设为 -1，只有从源点可以到达的顶点会被赋予非负值，其中源点 h[s] 被设为 0，之后每经过一条残留边，层次增加 1。

  • 构造层次图：在 BFS 遍历中，只有那些具有正残量的边会被考虑，因此 h 数组实际构造了一个“层次图”，使得 DFS 只沿着满足 h[v] == h[u] + 1 的边进行，从而提高搜索效率。

  • 确定最小割的 S 集合：当最大流求解完成后，最后一次 BFS 过程中仍然能到达的顶点，其 h 值不为 -1。这些顶点构成了 S 集合（即从源点 s 在残留网络中可以达到的所有顶点），而无法到达的顶点构成 T 集合。正是这种划分决定了最小割的边：所有从 S 到 T 的边，其总容量即为最小割的容量。

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
template<class T>
struct MaxFlow {
    const int n;
    struct Edge {
        int v;
        T cap;
        Edge(int v, T cap) : v(v), cap(cap) {}
    };

    vector<Edge> e;
    vector<vector<int>> g;
    vector<int> dep, cur;

    MaxFlow(int n) :n(n), g(n) {}

    bool bfs(int s, int t) {
        dep.assign(n, -1);
        queue<int> q;
        q.push(s);
        dep[s] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto i : g[u]) {
                auto [v, c] = e[i];
                if (c > 0 && dep[v] == -1) {
                    dep[v] = dep[u] + 1;
                    q.push(v);
                    if (v == t) return true;
                }
            }
        }
        return false;
    }

    T dfs(int u, int t, T flow) {
        if (u == t) return flow;
        T sum = 0;
        for (int i = cur[u]; i < g[u].size(); i++) {
            cur[u] = i;
            int j = g[u][i];
            auto& [v, c] = e[j];
            if (dep[v] == dep[u] + 1 && c > 0) {
                T f = dfs(v, t, min(c, flow));
                e[j].cap -= f;
                e[j ^ 1].cap += f;
                sum += f;
                flow -= f;
                if (flow == 0) break;
            }
        }
        if (sum == 0) dep[u] = 0;
        return sum;
    }

    T dinic(int s, int t) {
        T F = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            F += dfs(s, t, std::numeric_limits<T>::max());
        }
        return F;
    }

    vector<int> minCut() {
        vector<int> c(n);
        for (int i = 0; i < n; i++) {
            c[i] = (dep[i] == -1) ? 0 : 1;
        }
        return c;
    }

    void add(int u, int v, T c) {
        g[u].push_back(int(e.size()));
        e.emplace_back(v, c);
        g[v].push_back(int(e.size()));
        e.emplace_back(u, 0);
    }
};

举一个应用（求最小割边集合）

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
112
113
114
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
template<class T>
struct MaxFlow {
    const int n;
    struct Edge {
        int v;
        T cap;
        Edge(int v, T cap) : v(v), cap(cap) {}
    };

    vector<Edge> e;
    vector<vector<int>> g;
    vector<int> dep, cur;

    MaxFlow(int n) : n(n), g(n) {}

    bool bfs(int s, int t) {
        dep.assign(n, -1);
        queue<int> q;
        q.push(s);
        dep[s] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto i : g[u]) {
                auto [v, c] = e[i];
                if (c > 0 && dep[v] == -1) {
                    dep[v] = dep[u] + 1;
                    q.push(v);
                    if (v == t) return true;
                }
            }
        }
        return false;
    }

    T dfs(int u, int t, T flow) {
        if (u == t) return flow;
        T sum = 0;
        for (int i = cur[u]; i < g[u].size(); i++) {
            cur[u] = i;
            int j = g[u][i];
            auto& [v, c] = e[j];
            if (dep[v] == dep[u] + 1 && c > 0) {
                T f = dfs(v, t, min(c, flow));
                e[j].cap -= f;
                e[j ^ 1].cap += f;
                sum += f;
                flow -= f;
                if (flow == 0) break;
            }
        }
        if (sum == 0) dep[u] = 0;
        return sum;
    }

    T dinic(int s, int t) {
        T F = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            F += dfs(s, t, std::numeric_limits<T>::max());
        }
        return F;
    }

    vector<int> minCut() {
        vector<int> c(n);
        for (int i = 0; i < n; i++) {
            c[i] = (dep[i] == -1) ? 0 : 1;
        }
        return c;
    }

    void add(int u, int v, T c) {
        g[u].push_back(int(e.size()));
        e.emplace_back(v, c);
        g[v].push_back(int(e.size()));
        e.emplace_back(u, 0);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s, t;
    cin >> n >> m >> s >> t;

    MaxFlow<i64> mf(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        i64 w;
        cin >> u >> v >> w;
        mf.add(u, v, w);
    }

    i64 k = mf.dinic(s, t);
    vector<int> p = mf.minCut();
    cerr << k << '\n';
    i64 cut = 0;
    for (int i = 0; i < n; i++) {
        if (p[i]) {
            for (auto j : mf.g[p[i]]) {
                auto [v, w] = mf.e[j];
                if (!p[v]) {
                    cut += w;
                }
            }
        }
    }
    cout << k << ' ' << cut << '\n';
    return 0;
}