夢に僕らで帆を張って
来るべき日のために夜を超え

标签 Kruskal重构树 下的文章

October 30, 2019

洛谷P4768/NOI2018 归程

题意略数据范围:$n \le 200000,m \le 400000,q \le 400000$ [强制在线]题解分析题意:需要找到一个节点$u$,使得从起点$v \rightarrow u$上的所有节点的海拔$> p$,并且使得从$u \rightarrow 1$距离最小第一个要求可以用$\mathrm{Kruskal}$重构树解决(以海拔为关键字降序建立);因为重构树是小根堆,所以...
October 30, 2019

洛谷P1967 货车运输

题意多个询问,求两点间所有路径中最小边权的最大值数据范围:$0 < n < 10000,0 < m < 50000,0 < q < 30000,0 \le z \le 100000$题解求两点间所有路径中最小边权的最大值,可用$\mathrm{Kruskal}$重构树两点间所有路径中最小边权的最大值即为在重构树上其$\mathrm{LCA}$的点权注:可能...