U92652

【模板】kruskal重构树

题目描述

给出一个有 $n$ 个结点， $m$ 条边的无向图，每条边有一个边权。

求结点 $x,y$ 之间所有路径的中，最长的边最小值是多少，若这两个点之间没有任何路径，输出 -1 。

共有 $Q$ 组询问。

输入格式

第一行三个整数 $n,m,Q$ 。

接下来 $m$ 行每行三个整数 $x,y,z(1 \le x,y \le n,1 \le z \le 1000000)$ ，表示有一条连接 $x$ 和 $y$ 长度为 $z$ 的边。接下来 $Q$ 行每行两个整数 $x,y(x \neq y)$ ，表示一组询问。

输出格式

$Q$ 行，每行一个整数，表示一组询问的答案。

输入输出样例

输入样例 #1

输出样例 #1

说明/提示

对于 $100\%$ 的数据，满足 $1 \le n,m,Q \le 300000$ 。保证不存在自环，但可能存在重边。

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

U92652 【模板】kruskal重构树题解 Author: Yuyi 题意分析题目要求在一张无向图中，对于 $Q$ 组询问 $(x,y)$，求出所有从 $x$ 到 $y$ 的路径中，单条边权最大值的最小值。如果两点不连通，则输出 1 。这又是最小生成树家族里的一个经典模板—— Kruskal 重构树！它的思想非常巧妙：在普通的 Kruska…

点击展开完整题解点击收起题解

2026年8月9日 22:37

U92652 【模板】kruskal重构树题解

Author: Yuyi

题意分析

题目要求在一张无向图中，对于 $Q$ 组询问 $(x,y)$ ，求出所有从 $x$ 到 $y$ 的路径中，单条边权最大值的最小值。如果两点不连通，则输出 -1。这又是最小生成树家族里的一个经典模板——Kruskal 重构树！

它的思想非常巧妙：在普通的 Kruskal 加边过程中，当我们因为一条边 $w$ 合并了两个连通块（假设两块的根节点分别为 $u$ 和 $v$ ）时，我们不直接在 $u$ 和 $v$ 之间连边。而是新建一个虚拟节点，将这个虚拟节点的权值赋为 $w$ 。然后让这个新节点作为 $u$ 和 $v$ 的父亲。这样一来，在加了 $N-1$ 条边后，原本的图就变成了一棵二叉树（或者森林），原本的 $N$ 个点全都是叶子节点，而新建的 $N-1$ 个点则是带有边权内部节点。根据这个构造方式，这棵树的点权从叶子到根是严格递增的（因为 Kruskal 是按边权从小到大加边的，也就是个大根堆）。因此，任意两个叶子节点 $x$ 和 $y$ 在树上的 LCA（最近公共祖先）的点权，就是它们在原图中连通所需的瓶颈边，也就是所有路径中“最大边权的最小值”！

正解推导过程

初始化：读取所有边，按照边权从小到大排序。
Kruskal 重构：
- 设当前总结点数 tot = N。
- 遍历排好序的边，利用并查集找两端点的祖先 $fu$ 和 $fv$ 。
- 如果 $fu \neq fv$ ，说明要合并。此时 tot++ 创建一个新节点，其权值 val[tot] = 边权。
- 在树形结构中，将 tot 设为 $fu$ 和 $fv$ 的父亲，即把 $fu$ 和 $fv$ 作为 tot 的左右儿子。
- 在并查集中，fa[fu] = tot, fa[fv] = tot。
LCA 预处理：对重构出来的树（或者森林），从所有的根节点出发跑一遍 DFS，求出所有节点的深度 dep 以及用于倍增求 LCA 的数组 f[i][j]。
处理询问：对于每对 $(x,y)$ ，先用并查集的 find 看看它们在不在同一个连通块里，不在就输出 -1；在的话直接用倍增求出它们的 LCA 节点，然后输出 val[lca]。

正解代码及分析

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 600005; // 点数N加上虚拟节点N-1，最多 2N 个点，约 60万
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n,m,q;
struct Edge
{
    int u,v,w;
}e[maxn];
bool cmp(Edge A,Edge B)
{
    return A.w < B.w;
}
int fa[maxn];
int find(int u)
{
    if(u == fa[u]) return u;
    return fa[u] = find(fa[u]);
}
int val[maxn];
int ch[maxn][2];
int dep[maxn];
int f[maxn][20];
void dfs(int u,int father)
{
    dep[u] = dep[father] + 1;
    f[u][0] = father;
    rep(i,1,19) f[u][i] = f[f[u][i-1]][i-1];
    if(ch[u][0]) dfs(ch[u][0],u);
    if(ch[u][1]) dfs(ch[u][1],u);
}
int lca(int x,int y)
{
    if(dep[x] < dep[y]) swap(x,y);
    dep(i,19,0)
    {
        if(dep[f[x][i]] >= dep[y]) x = f[x][i];
    }
    if(x == y) return x;
    dep(i,19,0)
    {
        if(f[x][i] != f[y][i])
        {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
void solve()
{
    read(n),read(m),read(q);
    rep(i,1,m) read(e[i].u),read(e[i].v),read(e[i].w);
    sort(e+1,e+1+m,cmp);
    rep(i,1,n*2) fa[i] = i; 
    int tot = n; 
    rep(i,1,m)
    {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if(fu != fv)
        {
            tot++;
            val[tot] = e[i].w; // 虚拟节点的点权即为边权
            ch[tot][0] = fu;
            ch[tot][1] = fv;
            fa[fu] = tot;
            fa[fv] = tot;
        }
    }
    rep(i,1,tot)
    {
        if(fa[i] == i) dfs(i,0); // 找到每棵树的根节点，向下预处理倍增数组
    }
    while(q--)
    {
        int u,v;
        read(u),read(v);
        if(find(u) != find(v)) cout << -1 << '\n'; // 30万次询问，为防止TLE，此处作特殊情况处理，使用\n替换endl
        else cout << val[lca(u,v)] << '\n';
    }
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：Kruskal 对边进行排序耗时 $O(M \log M)$ 。构建重构树过程极快接近 $O(M)$ 。建好树后预处理 DFS 的倍增数组复杂度为 $O(N \log N)$ 。最后的 $Q$ 组询问，每次查询 LCA 的耗时是 $O(\log N)$ ，总共 $O(Q \log N)$ 。综合下来时间复杂度被稳定控制在 $O(M \log M + Q \log N)$ 的量级。
空间复杂度：对于最大 $300,000$ 个点的图，连同重构树生成的虚拟节点，总结点数逼近 $600,000$ 个。代码严格统一使用 maxn = 600005，其中消耗最大的是 LCA 算法需要的 f[maxn][20] 数组，它大约吃掉 48 MB 左右内存。在普通比赛 128M / 256M 的内存限制下绰绰有余，空间复杂度为 $O(N \log N)$ ，完美过关。

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。