最小割树学习笔记

口胡

定义

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

构造

每次任选两个节点，求最小割，最小割把这张图分成了两个部分，然后对这两个部分分别递归构造, 复杂度 $O(n^3m)$ , 跑不满。

性质

设 $\lambda(a, b)$ 表示 $a$ 和 $b$ 的最小割

性质 $1$

设 $V_u$ 和 $V_v$ 表示边 $(u, v)$ 两端的部分, 那么对于 $x \in V_u$ 和 $y \in V_v$, 有 $\lambda(x, y) \leq \lambda(u, v)$ .

证明：

因为 $x$ 和 $y$ 分别在被 $(u, v)$ 的最小割分成的两部分中，所以 $\lambda(u, v)$ 是 $(x, y)$ 的割, 所以 $\lambda(x, y) \leq \lambda(u, v)$

性质 $2$

对于三个点 $a, b, c$ ， 有 $\lambda(a, b) \geq \min(\lambda(b, c), \lambda(a, c))$

证明：

在割掉 $(a, b)$ 后，$c$ 如果在 $a$ 那边，根据性质 $1$ , 有 $\lambda(b, c) \leq \lambda(a, b)$ ，如果在 $b$ 那边, 有 $\lambda(a, c) \leq \lambda(a, b)$ ，所以一定有 $\lambda(a, b) \geq \min(\lambda(b, c), \lambda(a, c))$

性质 $3$

由性质 $2$ 可以得到 $\lambda(a, b) \geq \min(\lambda(a, p_1), \lambda(p_1, p_2), \lambda(p_2, p_3), ... \lambda(p_k, b))$

性质 $4$ （最重要）

设 $(p, q)$ 为最小割树 $x$ 到 $y$ 路径上的两点，且 $\lambda(p, q)$ 最小, 那么 $\lambda(x, y) = \lambda(p, q)$ , 即 $\lambda(x, y)$ 等于最小割树上 $x$ 到 $y$ 的路径上权值最小的边.

证明:

因为 $x$ 和 $y$ 在 $(p,q)$ 两侧, 所以有 $\lambda(x, y) \leq \lambda(p, q)$

由性质 $3$ 得 $\lambda(x, y) \geq \lambda(p, q)$

所以 $\lambda(x, y) = \lambda(p, q)$

Code

//网络流
int bfs(int S, int T) {
    memset(dep, 0, sizeof(dep));
    memcpy(cur, head, sizeof(head));
    q[h = t = 1] = S;
    dep[S] = 1;
    while (h <= t) {
        int u = q[h++];
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (!dep[v] && c[i]) {
                dep[v] = dep[u] + 1;
                q[++t] = v;
            }
        }
    }
    return dep[T];
}

int dfs(int u, int T, int lim) {
    if (u == T || !lim) return lim;
    int flow = 0, k;
    for (int i = cur[u]; i && lim; i = nxt[i]) {
        cur[u] = i;
        int v = to[i];
        if (dep[v] == dep[u] + 1 && c[i]) {
            k = dfs(v, T, min(lim, c[i]));
            if (!k) dep[v] = 0;
            lim -= k, flow += k;
            c[i] -= k, c[i ^ 1] += k;
        }
    }
    return flow;
}

int dinic(int S, int T) {
    for (int i = 2; i <= e_tot; ++i) {
        c[i] = c[i] + c[i ^ 1];
        c[i ^ 1] = 0;
    }
    int res = 0;
    while (bfs(S, T)) res += dfs(S, T, inf);
    return res;
}

//构造最小割树
void solve(int l, int r) {
    if (l == r) return ;
    int S = node[l], T = node[l + 1];
    int cut = dinic(S, T);
    link(S, T, cut);
    link(T, S, cut);
    int tot1 = 0, tot2 = 0;
    for (int i = l; i <= r; ++i) {
        if (dep[node[i]]) tmp1[++tot1] = node[i];
        else tmp2[++tot2] = node[i];
    }
    for (int i = 1; i <= tot1; ++i) node[l - 1 + i] = tmp1[i];
    for (int i = 1; i <= tot2; ++i) node[l + tot1 - 1 + i] = tmp2[i];
    solve(l, l + tot1 - 1);
    solve(l + tot1, r);
}

void dfs(int u, int _fa) {
    dep[u] = dep[_fa] + 1;
    for (auto it : path[u]) {
        int v = it.first, len = it.second;
        if (v == _fa) continue;
        minn[v][0] = len, fa[v][0] = u;
        dfs(v, u);
    }
}

// 查询任意两点的最小割
int query(int x, int y) {
    int res = 0x3f3f3f3f;
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 10; ~i; --i) {
        if (dep[fa[x][i]] >= dep[y]) {
            res = min(res, minn[x][i]);
            x = fa[x][i];
        }
    }
    if (x == y) return res;
    for (int i = 10; ~i; --i) {
        if (fa[x][i] != fa[y][i]) {
            res = min(res, minn[x][i]);
            res = min(res, minn[y][i]);
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    res = min(res, minn[x][0]);
    res = min(res, minn[y][0]);
    return res;
}

例题

【模板】最小割树（Gomory-Hu Tree）

题目 代码

[ZJOI2011]最小割

题目 代码

[CQOI2016]不同的最小割

题目 代码