Dyd's Blog

He who has a strong enough why can bear almost any how.

最小割树

Posted on In
Symbols count in article: 4.1k Reading time ≈ 4 mins.

一种快速求多次最小割的办法

最小割树

即 Gomory-Hu Tree ，是用来解决无向图最小割的问题的

最小割

一个无向图的最小割是对于两个点来说的，形式化的：

对于无向图 $G = (V, E)$ ，若 $x, y \in V$ ，且存在边集 $S \sqsubseteq E$ ，使得删去 $S$ 后点 $x, y$ 不再联通，则称 $S$ 为 $x, y$ 的一个割；定义 $S$ 的权值为其中所有边权和，在所有的割中，权值最小的就叫做最小割

感性理解就是删掉权值和尽可能小的边，使得两点不联通

最大流最小割定理

在一个网络流中，能够从源点到达汇点的最大流量等于如果从网络中移除就能够导致网络流中断的边的集合的最小容量和，即在任何网络中，最大流的值等于最小割的容量

证明略

最小割树

定义一棵树 $T$ 为最小割树，如果对于树上的所有边 $(s,t)$ ，树上去掉 $(s,t)$ 后产生的两个集合恰好是原图上 $(s,t)$ 的最小割把原图分成的两个集合，且边 $(u,v)$ 的权值等于原图上 $(u,v)$ 的最小割

感性来说，就是一种特殊的树，树上两点路径上的最小权值就是原图两点的最小割

构造

最小割树的构造是递归实现的，假设递归到了点集 $P$ ，我们任取 $x, y \in P$ ，对它们做一次最小割，设答案为 $ans$ ，然后在树上连边 $(x, y, ans)$ ；去掉最小割中的边后， $P$ 必然被分成两个不联通的子集 $S_1, S_2$ ，我们递归处理 $S_1, S_2$ 即可，时间 $O(n \times 网络流)$ ，这里用 Dinic ，是 $O(n^3 m)$ ，跑不满（尤其是我们每次随机选两个点，很不好卡）

关于“树上两点路径上的最小权值就是原图两点的最小割”，可以感性理解一下，证明自己 baidu 吧

代码

以这个题为例

实现时有个技巧，我们可以利用 Dinic 的最后一次 bfs 得到的分成来判断每个点在那个联通图中

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
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
#define STC static
const int N = 500 + 100, M = 1500 + 100, INF = 0x3f3f3f3f;
int n, m, Q;
struct Edge{ int ne, ver, w; };
namespace Dinic
{
    int cur[N], dep[N], S, T, idx = 0, h[N];
    Edge e[M << 2];
    void add(int x, int y, int z){ e[idx] = {h[x], y, z}, h[x] = idx++; }
    void dad(int x, int y, int z){ add(x, y, z), add(y, x, 0); }
    void init(int _s, int _t)
    {
        S = _s, T = _t;
        for (int i = 0; i < idx; i += 2) e[i].w = (e[i].w + e[i ^ 1].w), e[i ^ 1].w = 0;
    }
    bool bfs()
    {
        memset(dep, 0, sizeof dep);
        std::queue<int> q;
        for (q.push(S), dep[S] = 1, cur[S] = h[S]; !q.empty(); )
        {
            int x = q.front(); q.pop();
            for (int i = h[x], y; ~i; i = e[i].ne) if (!dep[y = e[i].ver] && e[i].w)
            {
                dep[y] = dep[x] + 1, cur[y] = h[y];
                if (y == T) return true;
                q.push(y);
            }
        }
        return false;
    }
    int find(int x, int lim)
    {
        if (x == T) return lim;
        int t, y, flow = 0;
        for (int i = cur[x]; ~i && flow < lim; i = e[i].ne)
        {
            cur[x] = i;
            if (dep[y = e[i].ver] == dep[x] + 1 && e[i].w)
            {
                if (!(t = find(y, std::min(lim - flow, e[i].w)))) dep[y] = -1;
                e[i].w -= t, e[i ^ 1].w += t, flow += t;
            }
        }
        return flow;
    }
    int dinic(int _s, int _t) //本题不用开long long
    {
        init(_s, _t);
        int res = 0, flow;
        while (bfs()) while (flow = find(S, INF)) res += flow;
        return res;
    }
}
namespace GHT //Gomory-Hu Tree
{
    const int D = 10;
    int nd[N], h[N], idx = 0, dep[N], f[N][D], mn[N][D];
    std::default_random_engine eee{114514};
    Edge e[N << 1];
    void add(int x, int y, int z){ e[idx] = {h[x], y, z}, h[x] = idx++; }
    void build(int l, int r)
    {
        if (l == r) return ;
        STC int tp1[N], tp2[N];
        int s, t, flow, ct1 = 0, ct2 = 0;
        s = nd[l], t = nd[l + 1];
        flow = Dinic::dinic(s, t);
        add(s, t, flow), add(t, s, flow);
        for (int i = l; i <= r; ++i) (Dinic::dep[nd[i]] ? tp1[++ct1] : tp2[++ct2]) = nd[i];
        for (int i = 1; i <= ct1; ++i) nd[i + l - 1] = tp1[i];
        for (int i = 1; i <= ct2; ++i) nd[i + l + ct1 - 1] = tp2[i];
        build(l, l + ct1 - 1), build(l + ct1, r);
    }
    void bfs()
    {
        std::queue<int> q;
        for (q.push(1), dep[1] = 1; !q.empty(); )
        {
            int x = q.front(); q.pop();
            for (int i = h[x], y; ~i; i = e[i].ne) if (!dep[y = e[i].ver])
            {
                dep[y] = dep[x] + 1, f[y][0] = x, mn[y][0] = e[i].w;
                q.push(y);
            }
        }
        for (int j = 1; j < D; ++j)
            for (int i = 1; i <= n; ++i)
            {
                mn[i][j] = std::min(mn[i][j - 1], mn[f[i][j - 1]][j - 1]);
                f[i][j] = f[f[i][j - 1]][j - 1];
            }
    }
    void work()
    {
        for (int i = 1; i <= n; ++i) nd[i] = i;
        shuffle(nd + 1, nd + 1 + n, eee); //随机化
        build(1, n), bfs();
    }
    int ask(int x, int y)
    {
        int res = INF;
        if (dep[x] > dep[y]) std::swap(x, y);
        for (int i = D - 1; i >= 0; --i) if (dep[f[y][i]] >= dep[x]) res = std::min(res, mn[y][i]), y = f[y][i];
        if (x == y) return res == INF ? -1 : res;
        for (int i = D - 1; i >= 0; --i) if (f[x][i] != f[y][i])
        {
            res = std::min(res, std::min(mn[x][i], mn[y][i]));
            x = f[x][i], y = f[y][i];
        }
        res = std::min(res, std::min(mn[x][0], mn[y][0]));
        return res == INF ? -1 : res;
    }
}
int main() //因为数据有误,给定图的真实点数应该是n+1个,编号为0到n
{

    memset(Dinic::h, -1, sizeof Dinic::h);
    memset(GHT::h, -1, sizeof GHT::h);
    scanf("%d %d", &n, &m), ++n; //更正标号
    for (int i = 1, u, v, w; i <= m; ++i) scanf("%d %d %d", &u, &v, &w), Dinic::dad(++u, ++v, w), Dinic::dad(v, u, w);
    GHT::work();
    scanf("%d", &Q);
    for (int u, v; Q--; printf("%d\n", GHT::ask(++u, ++v))) scanf("%d %d", &u, &v);
    return 0;
}

另外，本题 $n$ 小而 $Q$ 大，可以处理出 $n^2$ 询问存下来，直接回答，就不必用树上倍增了