前言
azui大牛在讲课, 听到这个东西就搜索了一发, 貌似很有意思…
Kruskal重构树
对于一个无向图, 我们把所有边从小到大排序, 每次取出一条边然后新建辅助节点, 该节点权值为边权, 然后把这条边联通的两个联通块的kruskal重构树作为这个节点的左右儿子, 从而形成一个新的Kruskal重构树。
然后这个东东有这些性质:
1.是一颗二叉树
2.是一个大根堆
3.原树上两点间路径的点权对应原图见两点路径间最小边权
4.原无向图上两点(u, v)之间最长边的最小值为Kruskal重构树上两点LCA的权值
没了。
例题
BZOJ 3551
还没做…
Join the discussion