zcmimi's blog

arrow_backkruskal重构树共3篇文章

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

kruskal重构树模板

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

先想想暴力做法:

bfs出不涉水可以到达的点,然后在这些点中找出与点1的最小距离

优化:

我们可以使用kruskal重构树来快速求出这些点

先按海拔从高到低排序,这样见出来的kruskal重构树的是海拔的小根堆

我们可以倍增找出最远可以到达的祖先,然后求出这段区间中的点与点1的最小距离

可以在dfs的时候预处理

详见代码

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

可以算是kruskal重构树的模板题

建完kruskal重构树,我们可以发现一个节点(新建的带点权的点)能走到的节点一定在它的子树中

那么我们可以用dfs序+主席树维护

kruskal重构树

我们回想一下kruskal生成最小生成树的过程:

先将边按边权从小到大排序,然后依次加入

如果x,y已经联通,则跳过这条边

否则连接x,y

kruskal重构树是在kruskal生成最小生成树的,

连接x,y时,将边权变成一个新的节点t权值为边权,然后连边> t\rightarrow x,t\rightarrow y

代码:

1/1
Search
search