Kruskal重构树 学习笔记

适用场合

多次询问在一个图中，两个点之间的最短路上的最长边。这个题有多种解法，用 Kruskal 重构树的方法当然也能解决。

参考了这个 dalao 的博客

主要思想

建一个新的树：

• 按照 Kruskal 算法依次遍历边，当要进行合并时，再执行以下操作
• 把最小生成树上的边 $(u, v, w)$ 当作新的点，权值为原来边权 $w$
• 分别两条边连向 $u$、$v$ 所在的子树的根节点

求两个点 $x, y$ 之间最短路上的最长边，等价于在新的树上 $LCA(x, y)$ 的权值。

代码

这个是用来解决货车运输的代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxN = 1e5 + 7;

int n, m, q, cnt, head[maxN], fa[maxN], tot, val[maxN], f[maxN][21], depth[maxN];

struct Edge {
    int from, to, dis;
}e[maxN << 1], initEdge[maxN];

inline void add(int u, int v)
{
    e[++cnt].from = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}

int Find(int x)
{
    return fa[x] == x? x : fa[x] = Find(fa[x]);
}

bool cmp(Edge x, Edge y)
{
    return x.dis > y.dis;
}

void dfs(int x)
{
    for(int i = head[x]; i; i = e[i].from) {
        int y = e[i].to;
        f[y][0] = x; depth[y] = depth[x] + 1;
        dfs(y);
    }
}

inline void KruskalTree()
{
    sort(initEdge + 1, initEdge + 1 + m, cmp);
    for(int i = 1; i <= n; ++i)
        fa[i] = i;
    tot = n; //tot记录的是新的图上点的个数   
    for(int i = 1; i <= m; ++i) {
        int fx = Find(initEdge[i].from), fy = Find(initEdge[i].to);
        if(fx == fy)
            continue;
        val[++tot] = initEdge[i].dis; //建立新的树
        fa[tot] = fa[fx] = fa[fy] = tot;
        add(tot, fx); add(tot, fy);
    }
}

inline void initLca() //从这开始就是普通的LCA了
{
    for(int i = tot; i >= 0; --i) //这个地方要倒序,因为tot是根节点
        if(!depth[i])
            dfs(i);
    for(int j = 1; (1 << j) <= tot; ++j)
        for(int i = 1; i <= tot; ++i)
            f[i][j] = f[f[i][j - 1]][j - 1];
}

int Lca(int x, int y)
{
    if(depth[x] < depth[y])
        swap(x, y);
    int t = (int)(log(depth[x]) / log(2)) + 1;
    for(int i = t; i >= 0; i--)
        if(depth[f[x][i]] >= depth[y])
            x = f[x][i];
    if(x == y)
        return x;
    for(int i = t; i >= 0; i--)
        if(f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];             
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i)
        scanf("%d%d%d", &initEdge[i].from, &initEdge[i].to, &initEdge[i].dis);
    KruskalTree();
    initLca();
    scanf("%d", &q);
    while(q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if(Find(x) != Find(y)) //当然图可能不连通
            printf("-1\n");
        else
            printf("%d\n", val[Lca(x, y)]);    
    }
    return 0;
}