「算法笔记」Kruskal 重构树

自从做了「NOI 2018」归程 之后,才知道有 $\text{Kruskal}$ 重构树这个冷门又神奇的东西。


概述

$\text{Kruskal}​$ 重构树是基于 $\text{Kruskal}​$ 最小生成树算法的一种算法,它主要通过将边权转化为点权来实现,其中有一些非常奇妙的性质!


构造

除了连边,其他过程都和 $\text{Kruskal}$ 最小生成树算法完全一样。

当我们需要在 $u,v$ 之间连一条权值为 $w$ 的边时,$\text{Kruskal}$ 重构树算法是这样实现的:

  • 新建节点 $x$,将 $x$ 的点权设为 $w$。
  • 设 $u,v$ 所属集合分别为 $S_u$ 和 $S_v$,那么连边 $(x,S_u)$ 和 $(x,S_v)$,此处连有向边即可,注意没有边权!
  • 将 $u$ 和 $v$ 所属集合都改为 $x$。

其余过程直接套用 $\text{Kruskal}$ 即可!

重构树的根应该为 $2n-1$,也就是最后一个点。原因为:如果以 $1\sim n$ 中的任何一个点作为根会破坏重构树的形态;连边时向下连边,只有以 $2n-1$ 为根时才能遍历整棵树。

构造重构树的复杂度和 $\text{Kruskal}$ 一样,都是 $\mathcal O(n\log n)$。


性质

  1. 最后形成一棵有 $2n-1$ 个节点的树。

我们需要将 $n$ 个原来的点最后放到同一个集合中,那么需要进行 $n-1$ 次合并。每次合并都会新建 $1$ 个节点和 $2$ 条无向边。那么一共会有 $2n-1$ 个点和 $2n-2$ 条边。

  1. 重构树中的叶子节点为原树中的节点,其余每个节点代表了一条边。

我们每次将 $x$ 和下方的 $u,v$ 连边,这个证明很显然吧!

  1. 原树 $u$ 到 $v$ 路径上的边权最大值为重构树上 $u$ 和 $v$ 的 $\text{LCA}$ 的点权。

根据 $\text{Kruskal}$ 的过程,我们把边按照权值从小到大排序,那么对于所有非叶子节点,它的点权(原图的边权)一定不大于父亲节点的点权,所以路径上的最大值即为 $\text{LCA}$ 的点权。


例题

本文以「BZOJ 3732」Network 为例(虽然此题可以直接用倍增解决,但是这里使用 $\text{Kruskal}$ 重构树的方法实现)

Description

给你 $n$ 个点 $m$ 条边的无向图,每条边的长度为 $d_i$。现在有 $k$ 个询问 ,每次询问 $u,v$ 之间的所有路径中,最长边的最小值是多少?

数据范围:$1\le n\le 1.5\times 10^4$,$1\le m\le 3\times 10^4$,$1\le k\le 2\times 10^4$,$1\le d_i\le 10^9$

Solution

首先我们可以发现一个性质:最长边最小的路径一定在这张图的最小生成树上。那么我们只要求出这张图的最小生成树,然后倍增求出最大值即可。

然而现在不是讨论倍增的时候!

我们不建立最小生成树,而是建立重构树。根据上面的性质 $(3)$,每次询问的答案就是 $\text{LCA}(u,v)$ 的点权。

时间复杂度:$\mathcal O(m\log m+k\log n)$

Code

#include <cstdio>
#include <algorithm>

const int N = 3e4 + 5, M = 6e4 + 5, logN = 16;

int n, m, q, tot, fa[N], lnk[N], ter[M], nxt[M], val[N], f[N][logN], dep[N];

struct Edge {
    int u, v, w;
    bool operator<(const Edge &b) const {
        return w < b.w;
    }
} e[M];

void add(int u, int v) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void kruskal() {
    std::sort(e + 1, e + m + 1);
    int lim = n + n;
    for (int i = 1; i <= lim; i++) fa[i] = i;
    for (int idx = n, i = 1; i <= m; i++) {
        int fu = find(e[i].u), fv = find(e[i].v);
        if (fu == fv) continue;
        fa[fu] = fa[fv] = ++idx, val[idx] = e[i].w;
        add(idx, fu), add(idx, fv);
        if (idx == lim - 1) break;
    }
}
void dfs(int u, int p) {
    dep[u] = dep[p] + 1, f[u][0] = p;
    for (int i = 1; (1 << i) <= dep[u]; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == p) continue;
        dfs(v, u);
    }
}
int lca(int u, int v) {
    if (dep[u] < dep[v]) std::swap(u, v);
    int d = dep[u] - dep[v];
    for (int i = 15; ~i; i--) if (d & (1 << i)) u = f[u][i];
    if (u == v) return u;
    for (int i = 15; ~i; i--) if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    }
    kruskal();
    dfs(n + n - 1, 0);
    for (int i = 1; i <= q; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        printf("%d\n", val[lca(u, v)]);
    }
    return 0;
}

习题

发表评论