实际上是一个最短路问题,但加上了海拔这个条件限制,要在海拔<水位线p中找最短路。 这里使用Kruskal重构树,将其按海拔建成小根堆,我们就可以在树中用倍增找出他不得不下车的点;树中节点有两个权值L(最短...
洛谷题目链接:[NOI2018]归程 因为题面复制过来有点炸格式,所以要看题目就点一下链接吧\(qwq\) 题意: 在一张无向图上,每一条边都有一个长度和海拔高度,小\(Y\)的家在\(1\)节点,并且他有一部车,车只能在海拔高度大...
题目链接:点击查看 题目大意:去原网址看吧 题目分析:因为是在刷克鲁斯卡尔重构树的题目,所以稍微思考一下就能想出解法了,首先如果水位线固定了,剩下的边组成的最小生成树也是一定的,此时同一个连通块内的...