【图论】Kruskal重构树【算法竞赛入门笔记】

我能看懂吗？（前置内容）

最小生成树、Kruskal 算法、LCA 等。~（看不懂可以自己查）~

什么是 Kruskal 重构树？（定义）

在 Kruskal 算法进行中，我们会按顺序加边，而且每次加边会合并两个节点集合。

现在，我们有一个 N 个节点 E 条边的无向连通图。我们创造一个全是二叉树的森林。初始状态下，它有 N 个节点，分别表示无向图中的每个节点；没有边。

让我们的读者自己画图吧。~（不要像 Sukilin 一样走马观花）（绝对不是 Sukilin 不想放图）~

接下来跑 Kruskal。在 Kruskal 算法中每加一条边，我们就在森林上新增一个节点，并使这个节点的左、右孩子，分别为原图中新加的这条边的两个端点，在这个森林里所在的连通块的树根；使这个节点的点权，等于 Kruskal 算法中新加的这条边的边权。

跑完 Kruskal，我们的森林显然会变成一个有 N 个叶子、共 2N - 1 个节点的二叉树，而且每个非叶子节点都有两个孩子。

它就是这个无向连通图的 Kruskal 重构树。

已阅，有意义吗？（性质）

1. 显然 Kruskal 重构树的点权符合大根堆。
2. 显然 Kruskal 重构树的两个叶子的 LCA 的权值，等于最小生成树上这两个叶子对应的节点之间的简单路径上的最大的边权。而这个边权就是原图中这两个节点之间每条简单路径上的最大边权的最小值。

这里作出说明：运用反证法，设两个节点在最小生成树上的简单路径中的最大边权是 W，假设这条路径不符合上述条件。也就是存在另一条路径，上面的所有边权都小于 W。显然把边权为 W 的那条边删去，换成“另一条路径”中某一条不在最小生成树上的边（要保证换上之后能形成生成树。这是可以做到的，因为删去那条边之后最小生成树变成两个连通块，开头说的那两个节点分别位于两个连通块，所以“另一条路径”上肯定存在一条边把两个连通分量连起来），这个生成树的边权和比最小生成树还小，显然矛盾。

可能更好理解的角度：跑 Kruskal 加边的时候，加到某条边时，原图上两个节点恰好由不连通变为连通，那么这条边就是这两个节点间简单路径最大边权的最小值。

3. 也就是说，原图中，到一个给定的点 x 的简单路径的最大边权的最小值小于等于给定值 W 的所有点，在 Kruskal 重构树上全都在某一个子树内，而且包含了这个子树的所有叶子。于是，要想找到所有符合上述条件的节点，我们只需要找到 Kruskal 重构树上最浅的、权值小于等于 W 的非叶子节点。要想找到它，可以使用树上倍增（从 x 开始往上跳）。

已阅，但是这玩意能干啥？

让我们看例题。

板子

洛谷P1967 [NOIP2013 提高组] 货车运输

题面（形式化）

给定一个 n 个节点（编号从 1 到 n）m 条边（带权）的无向图（保证没有自环）。给出 q 个询问，每条询问包括两个节点的编号，求这两个节点之间的路径（如果有）中，最小边权的最大值。（如果没有，输出 -1）

思路

这里我们考虑使用 Kruskal 重构树的方法。

首先考虑一点点细节。这个图不一定连通，但是没关系，我们直接跑 Kruskal 然后最终的 “重构树” 是一个森林，每个连通块都有上述 Kruskal 重构树的性质；而且在 Kruskal 重构树（森林）里不连通的节点在原图也不连通（反之亦然）。

接下来，对于每个询问，在 Kruskal 重构树（森林）里求 LCA 即可。

注意我们要求最大生成树（森林），跑 Kruskal 要从大到小加边。

参考代码

原谅我的码风。

#include <iostream>
#include <cstdio>
#include <algorithm>
const int N = 1e4 + 7;
const int M = 5e4 + 7;
const int J = 30;
class edge {
    public:
        int tail;
        int head;
        int weight;
        friend bool operator < (edge x, edge y) {
            return x.weight < y.weight;
        }
        friend bool operator > (edge x, edge y) {
            return x.weight > y.weight;
        }
};
edge e[M];
int o;
int lch[N << 1], rch[N << 1]; //存 Kruskal 重构树
int wei[N << 1];
bool vis[N << 1];
int cnt;
int fak[J][N << 1], dep[N << 1]; //fak 是倍增求 LCA 的那个数组
int logn[N << 1];
int n, m;
int q;
int fas[N << 1]; //并查集的 fa 数组，维护 Kruskal 重构树的节点
inline void add(int x, int y, int w) {
    e[o++] = (edge){x, y, w};
}
int find(int x) {
    return x == fas[x] ? x : (fas[x] = find(fas[x]));
}
void kruskal() {
    std::sort(e, e + m, std::greater <edge>());
    for(int i = 0; i < m; i++) {
        int u = e[i].tail, v = e[i].head;
        u = find(u), v = find(v);
        if(u != v) {
            cnt++;
            fas[v] = cnt;
            fas[u] = cnt; //千万别写按秩合并
            lch[cnt] = u;
            rch[cnt] = v;
            wei[cnt] = e[i].weight;
        }
    }
}
//倍增 LCA 预处理
void init(int u, int f) {
    fak[0][u] = f;
    dep[u] = dep[f] + 1;
    for(int i = 1; i <= logn[dep[u]]; i++)
        fak[i][u] = fak[i - 1][fak[i - 1][u]];
    if(lch[u] != 0) init(lch[u], u);
    if(rch[u] != 0) init(rch[u], u);
}
//计算 LCA
int cal(int x, int y) {
    if(find(x) != find(y)) return -1; //不在一个连通块
  //在所在的连通块对应的 Kruskal 重构树查找
    int rt = find(x);
    if(!vis[rt]) init(rt, 0), vis[rt] = true; //预处理(每个连通块只需一次)
  //以下是倍增 LCA 板子
    if(dep[x] > dep[y]) std::swap(x, y);
    for(int i = logn[dep[y]]; i >= 0; i--)
        if(dep[fak[i][y]] >= dep[x])
            y = fak[i][y];
    if(x == y) return wei[x];
    for(int i = logn[dep[y]]; i >= 0; i--)
        if(fak[i][x] != fak[i][y])
            x = fak[i][x], y = fak[i][y];
    return wei[x == y ? x : fak[0][x]];
}
int main() {
    std::cin >> n >> m;
    cnt = n;
  //预处理以 2 为底的对数（倍增用的）
    logn[1] = 0;
    for(int i = 1; i <= n; i++)
        logn[i] = logn[i / 2] + 1;
    for(int i = 1; i <= 2 * n + 1; i++)
        fas[i] = i;
  //存图
    int x, y, z;
    for(int i = 0; i < m; i++) {
        std::cin >> x >> y >> z;
        add(x, y, z);
    }
    kruskal();
    std::cin >> q;
    for(int i = 0; i < q; i++) {
        std::cin >> x >> y;
        std::cout << cal(x, y) << '\n';
    }
    return 0;
}

杀死那个 SPFA

洛谷P4768 [NOI2018] 归程

题面

给定一个 n 个点 m 条边的无向连通图，每条边有两个边权：长度和海拔。给出 Q 个询问，每一个询问给定一个 v 和一个 p（强制在线）。定义海拔超过 p 的边为干边，海拔不超过 p 的边为湿边。求出所有从 v 开始只走干边能到的节点，与 1 号节点之间的所有路径中的最短长度。

思路

如何求从 v 开始只走干边能到的节点？考虑 Kruskal 重构树。（请参考“性质”第三条，这里不再赘述，注意仍然要从大到小加边。）

如何求这些节点到 1 号节点的路径长度最小值？先处理每个节点到 1 的最短路 ~（千万别用 SPFA）~。然后，在 Kruskal 重构树上，我们考虑维护：以每个节点为根节点的子树的叶子结点的“到 1 最短路长度”中的最小值。

注意 Kruskal 重构树是自底向上维护的。我们可以在加节点的时候直接处理好（取它两个子树的最小值）。

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
const int N = 2e5 + 7;
const int M = 4e5 + 7;
const int J = 20;
int logn[N << 1];
int T;
int n, m;
int last;
class edge {
    public:
        int u;
        int v;
        int l;
        int a;
        friend bool operator > (edge x, edge y) {
            return x.a > y.a;
        }
};
edge e[M];
int cnt;
int head[N], nex[M << 1], to[M << 1], len[M << 1];
inline void add(int u, int v, int l, int a) {
    nex[++cnt] = head[u];
    to[cnt] = v;
    len[cnt] = l;
    head[u] = cnt;
}
//最短路
class S {
    public:
        int d;
        int u;
        friend bool operator > (S a, S b) {
            return a.d > b.d;
        }
};
int mi[N << 1];
bool vis[N];
inline void dijkstra() {
    std::memset(vis + 1, false, n * sizeof(bool));
    std::memset(mi + 1, 0x3f, n * sizeof(int));
    std::priority_queue <S, std::vector <S>, std::greater <S> > heap;
    mi[1] = 0;
    heap.push((S){0, 1});
    while(!heap.empty()) {
        S c = heap.top();
        heap.pop();
        if(vis[c.u]) continue;
        vis[c.u] = true;
        for(int i = head[c.u]; i; i = nex[i]) {
            int v = to[i];
            if(vis[v]) continue;
            int w = len[i];
            if(mi[v] > mi[c.u] + w) {
                mi[v] = mi[c.u] + w;
                heap.push((S){mi[v], v});
            }
        }
    }
}
//Kruskal
int lch[N << 1], rch[N << 1], fas[N << 1], wei[N << 1];
int idx;
inline void init() {
    for(int i = 1; i <= n * 2 - 1; i++)
        fas[i] = i;
}
int find(int x) {
    return x == fas[x] ? x : (fas[x] = find(fas[x]));
}
inline void kruskal() {
    idx = n;
    std::sort(e + 1, e + 1 + m, std::greater<edge>());
    for(int i = 1; i <= m; i++) {
        int u = e[i].u;
        int v = e[i].v;
        u = find(u);
        v = find(v);
        if(u != v) {
            idx++;
            fas[u] = idx;
            fas[v] = idx;
            lch[idx] = u;
            rch[idx] = v;
            wei[idx] = e[i].a;
            mi[idx] = std::min(mi[u], mi[v]);
        }
    }
}
//树上倍增 
int fa[J][N << 1];
int dep[N << 1];
void dfs(int u, int f) {
    fa[0][u] = f;
    dep[u] = dep[f] + 1;
    for(int i = 1; i <= logn[dep[u]]; i++)
        fa[i][u] = fa[i - 1][fa[i - 1][u]];
    if(lch[u] != 0) dfs(lch[u], u);
    if(rch[u] != 0) dfs(rch[u], u);
}
inline int cal(int u, int w) {
    for(int i = logn[dep[u]]; i >= 0; i--)
        if(wei[fa[i][u]] > w) u = fa[i][u];
    return mi[u];
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    logn[1] = 0;
    for(int i = 2; i < N << 1; i++)
        logn[i] = logn[i / 2] + 1;
    std::cin >> T;
    for(int i = 0; i < T; i++) {
        last = 0;
        std::cin >> n >> m;
        cnt = 0;
        for(int j = 1; j <= m; j++) {
            int u, v, l, a;
            std::cin >> u >> v >> l >> a;
            add(u, v, l, a);
            add(v, u, l, a);
            e[j] = (edge){u, v, l, a};
        }
        dijkstra();
        init();
        kruskal();
        dfs(idx, 0);
        int q, k, s;
        std::cin >> q >> k >> s;
        for(int j = 0; j < q; j++) {
            int vv, pp, v, p;
            std::cin >> vv >> pp;
            v = (vv + k * last - 1) % n + 1;
            p = (pp + k * last) % (s + 1);
            std::cout << (last = cal(v, p)) << '\n';
        }
        std::memset(head, 0, sizeof(head));
        std::memset(to, 0, sizeof(to));
        std::memset(nex, 0, sizeof(nex));
        std::memset(lch, 0, sizeof(lch));
        std::memset(rch, 0, sizeof(rch));
        std::memset(dep, 0, sizeof(dep));
        std::memset(fa, 0, sizeof(fa));
    }
    return 0;
}