题面 [Luogu P4768] [NOI2018]归程 Solution 这题可能要用到Kruskal重构树的相关知识，如果有需求的同学可以看这里 首先，根据我们之前在运输计划那道题的经验，我们会发现我们开车能经过的边一定在以海拔为关键字的最大生成树上。 根据Kruskal重构树的性质：Kruskal重构树是一个堆，我们可以考虑这样做： 我们先把Kruskal重构树按每条路的海拔从大到小建出来，那么从某个点出发能开车到达的点一定是这个点的某个祖先的子树内的所有的点，这个很好理解，因为Kruskal重构树是一个堆，…
为什么要学Kruskal重构树 有时候，题目让我们多次求一个图的两点路径上最小值最大/最大值最小是多少。这种时候，根据一个比较显然的结论，我们可以把问题搬到一颗最小/最大生成树里面去做。 这个时候，我们当然可以倍增来搞这个问题。但在这里，我想向大家引入一种新的数据结构，它是基于kruskal求生成树的算法改来的，因此被称为Kruskal重构树。 什么是Kruskal重构树 这张图可以一目了然的介绍Kruskal重构树： 图出自https://blog.csdn.net/wu_tongtong/article/det…
最近评论
hilaolu 发布于 1 年前（03月16日）
Guava 发布于 2 年前（11月30日）
碱式碳酸希 发布于 2 年前（11月30日）
碱式碳酸希 发布于 2 年前（11月04日）
630分苦苦挣扎的菜鸡土豆 发布于 2 年前（05月01日）