专栏文章

kruskal重构树学习笔记

封封禁用户
个人记录参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqbegdw
此快照首次捕获于
2025/12/04 02:02
3 个月前
此快照最后确认于
2025/12/04 02:02
3 个月前
查看原文
我太菜了，所以只能把我学习过程中遇到的困难解释清楚。有笔误请狠狠的撅我。

什么是 kruskal 重构树

既然叫做 kruskal 重构树，那么肯定和 kruskal 有关系。
在普通的 kruskal 算法中，每次都选取最小的合法边组成生成树，而 kruskal 重构树每次选取最小的合法边构建树。
（图片）
kruskal 重构树是一种恰有 nn 个叶子结点，每个非叶子节点都恰有两个儿子节点的树。
那么这个树是怎么构建的呢？
相似地，将每条边按边权从小到大排序（因题目而异），每次选取边权最小的结点，新建一个点作为原边的两个子节点的各自父节点的父结点，kruskal 重构树没有边权，新建的结点的点权为原边的边权。
在维护这棵树的同时利用并查集维护连通块情况，以便判断剩下的边是否合法，以及新点插入时谁作它的子节点。
以 OI-wiki 上的图为例：
这个图的 kruskal 重构树是怎么来的呢？（方便起见，记连接 uu 和 vv 的边记作 (u,v)(u, v) 或 (v,u)(v, u)）
首先初始化时 fa[i]=ifa[i] = i，重构树为空。
从边权最小的边开始，首先是 (1,3)(1, 3)，发现 fa[1]=1fa[1] = 1，fa[3]=3fa[3] = 3，说明 11 和 33 不在同一个连通块中，就新建点 55，点 11 和 33 分别是它的两个子结点。（此时 fa[1]=5fa[1] = 5，fa[3]=5fa[3] = 5，fa[5]=5fa[5] = 5，55 号点点权为 11）
再遍历到边 (2,3)(2, 3)，发现 fa[2]=2fa[2] = 2，而 fa[3]=5fa[3] = 5。新建点 66 作为他们的父节点。此时 fa[1]=fa[3]=fa[2]=fa[6]=6fa[1] = fa[3] = fa[2] = fa[6] = 6，点 66 的点权为 22。
再到边 (1,2)(1, 2)，发现 fa[1]=fa[2]=6fa[1] = fa[2] = 6，不合法，跳过这条边。
最后到边 (3,4)(3, 4)，发现 fa[3]=6fa[3] = 6，而 fa[4]=4fa[4] = 4，新建点 77 作为他们的父节点，点 77 的点权为 44。现在所有点的 fafa 都是 77。于是这棵树就构建完了。
构建完的树长这样：
那么这棵树构建出来有什么用吗？

kruskal 重构树的性质

来自 OI-wiki：
不难发现，原图中两个点之间的所有简单路径上最大边权的最小值 == 最小生成树上两个点之间的简单路径上的最大值 == Kruskal 重构树上两点之间的 LCA 的权值。
也就是说，到点 xx 的简单路径上最大边权的最小值 ≤val\leq val 的所有点 yy 均在 Kruskal 重构树上的某一棵子树内，且恰好为该子树的所有叶子节点。
我们在 Kruskal 重构树上找到 xx 到根的路径上权值 ≤val\leq val 的最浅的节点。显然这就是所有满足条件的节点所在的子树的根节点。
如果需要求原图中两个点之间的所有简单路径上最小边权的最大值，则在跑 Kruskal 的过程中按边权大到小的顺序加边。
所以 kruskal 重构树经常配合 LCA 使用，可以用于解决限制走过路径中最小/大边权、求所需最小油量等问题。

P2245 星际导航

题目描述

sideman\text{sideman} 做好了回到 Gliese\text{Gliese} 星球的硬件准备，但是 sideman\text{sideman} 的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有 NN 个顶点和 MM 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。
sideman\text{sideman} 现在想把危险程度降到最小，具体地来说，就是对于若干个询问 (A,B)(A, B)，sideman\text{sideman} 想知道从顶点 AA 航行到顶点 BB 所经过的最危险的边的危险程度值最小可能是多少。作为 sideman\text{sideman} 的同学，你们要帮助 sideman\text{sideman} 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

输入格式

第一行包含两个正整数 NN 和 MM，表示点数和边数。
之后 MM 行，每行三个整数 AA，BB 和 LL，表示顶点 AA 和 BB 之间有一条边长为 LL 的边。顶点从 11 开始标号。
下面一行包含一个正整数 QQ，表示询问的数目。
之后 QQ 行，每行两个整数 AA 和 BB，表示询问 AA 和 BB 之间最危险的边危险程度的可能最小值。

输出格式

对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出 impossible\text{impossible}。

提示

对于 40%40\% 的数据，满足 N≤1000,M≤3000,Q≤1000N \leq 1000, M \leq 3000, Q \leq 1000。
对于 80%80\% 的数据，满足 N≤10000,M≤105,Q≤1000N \leq 10000, M \leq 10^5, Q \leq 1000。
对于 100%100\% 的数据，满足 N≤105,M≤3×105,Q≤105,L≤109N \leq 10^5, M \leq 3 \times 10^5, Q \leq 10^5, L \leq 10^9。数据不保证没有重边和自环。
求路径上所经过的边的边权最小值，想到 kruskal 重构树（但是这道题似乎不用也能做），重构完以后任意两点的 LCA 的点权就是途中的最大危险程度。
code（我不会树链剖分，所以写了倍增）：
CPP
#include<bits/stdc++.h>

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}

using namespace IO;
using namespace std;

const int maxn = 6e5 + 5;
const int maxm = 6e5 + 5;
const int maxp = 20 + 5;//倍增最大次幂

int n, m, A, B, Q;
int Edgetot;

struct Node {
	int fr, to, val;
	bool operator < (const Node & x) {
		return x.val > val;
	}
}Edge[maxm << 1];

void Edgeadd(int u, int v, int c) {
	Edgetot++;
	Edge[Edgetot].fr = u;
	Edge[Edgetot].to = v;
	Edge[Edgetot].val = c;
}

//以上是原图存储和操作，与链式前向星不同，存了每条边的端点和权值

int tot, hd[maxn], to[maxm << 1], nxt[maxm << 1], val[maxn << 1];

void add(int u, int v) {
	tot++;
	nxt[tot] = hd[u];
	hd[u] = tot;
	to[tot] = v;
}

//以上是重构树部分

int fa[maxn << 1], k;
int Find(int x) {
	return (x == fa[x]) ? x : fa[x] = Find(fa[x]);
}

int dep[maxn], fat[maxn][maxp];
int Posval[maxn << 1];
void dfs(int x, int father) {
	dep[x] = dep[father] + 1;
	fat[x][0] = father;
	for (int i = 1;i < maxp;i++) fat[x][i] = fat[fat[x][i - 1]][i - 1];
	
	for (int i = hd[x];i;i = nxt[i]) {
		int v = to[i];
		if (v == father) continue;
		dfs(v, x);
	}
}

int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i = maxp - 1;i >= 0;i--) if (dep[x] - (1 << i) >= dep[y]) {
		x = fat[x][i];
	}
	
	if (x == y) return x;
	
	for (int i = maxp - 1;i >= 0;i--) if (fat[x][i] != fat[y][i]) {
		x = fat[x][i];
		y = fat[y][i];
	}
	
	return fat[x][0];
}

int main() {
	n = read(), m = read();
	for (int i = 1;i <= m;i++) {
		int u = read(), v = read(), c = read();
		Edgeadd(u, v, c), Edgeadd(v, u, c);
	}
	
	sort(Edge + 1, Edge + 1 + m * 2);
	for (int i = 1;i <= n * 2;i++) fa[i] = i;k = n;

    for (int i = 1;i <= m * 2;i++) {
		int u = Edge[i].fr, v = Edge[i].to, Val = Edge[i].val;
		int Fau = Find(u), Fav = Find(v);
		if (Fau == Fav) continue;
		k++, fa[Fau] = k, fa[Fav] = k;
		add(k, Fau),add(k, Fav);
		Posval[k] = Val;
	}
	for (int i = 1;i <= k;i++) if (fa[i] == i) dfs(i, 0);
	Q = read();
	while (Q--) {
		int A = read(), B = read();
		if (Find(A) != Find(B)) puts("impossible");
		else write(Posval[LCA(A, B)]), putchar(10);
	}
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...