【每日一题】8月21日题目精讲-线路规划

题号 NC14419
名称线路规划
来源 Wannafly挑战赛4
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

首先，我们实际上是求一个最小生成树（原来树上的边是单向边，所以要实现两两双向通信，最后一个特别行动组内部成员新连的边还是得是一棵树）。
因为是最小生成树，考虑kruskal算法，要对边从小到大排序然后合并，所以先排上序再说。
然后来看这个给边的方法：X及X向上k个点和Y及Y向上k个点分别可以连一条长度为wi的边——直接暴力建边肯定会t，我们考虑将X向上长度为k的区间和Y向上长度为k的区间按2的次幂进行拆分（即对于X为起点长度为k的区间，将其以X为起点拆成若干个2^i的区间，比如，k=11 ，拆成长度为8，2，1的三个区间，其中长度为8的区间是包含X的）。我们对(X,Y,k,w)对应的若干个区间分别连边（在刚刚那个例子里即记录X向上长度为8的区间与Y向上长度为8的区间连一条边，再向上包含两个点的区间再连一条边，再向上一个点的区间，以此类推，这个操作需要用树上倍增去实现）。我们对“两个区间的连边”的操作记录的是最靠下的那个点和区间长度，（即可以定义一个数组edge[i]表示长度为2^i的区间有那些可以两两对应连边，edge[i]里面的每一个元素应该有三个量，x,y是两个区间的下端点，w是这个区间里面的点两两对应连边的权值。）用这样的方法，我们可以把题目给出的边整理到新的数组里面，他的好处是：统一了区间长度，保证了边长从小到大，且区间直接有倍增的包含关系（至于这个倍增关系怎么用，大家继续往下看）。
接下来，我们要考虑在这个做了整理之后的边的基础上跑kruskal（在做kruskal的时候维护出每个集合里的边长和，还有集合点数）。
首先，对于有边的两个区间，显然我们最下面的两个点XY如果没有在一个集合里面，肯定是要连在一起的，因为你连上面的再多点也不能改变XY没联通的事实，最直观的肯定是访问点深度最深边，但是这样边不好整理而且一条边连两个点究竟用什么来决定边的深度是不好说的，所以我们之前是按照区间大小整理，区间长度大的肯定相对靠下，即如果用的是同一组(x,y,k,w)关系那么上面的区间更短，但是这样会出现一个问题——区间长的边未必是最小边，先直接把它连起来的话会使得之后的短边可能就用不上了，比如有(3,4,4,10)和(3,4,2,1)两组边，我们先看(3,4,4,10)就会挤占掉(3,4,2,1)的机会，但是显然(3,4,2,1)更短。所以实际上我们对2^p值相等的边跑kruskal不是为把最后的树连出来，而是把当前这个2^p下完全没有用（已经被更好的边联通）的边扔掉，没有扔掉的边则加入下一层的kruskal，即我们对每一个2^p都单独建立生成树——所以对于当前p之下从edge里面拿出来的每一条边，我们判断他的两个下端点在当前p下有没有联通(下端点联通也有意味着整个区间都可以用这样长的边联通，不管是间接还是直接)，联通的话这条边直接舍弃，没联通的连上。连上之后，把这条边对应的区间一分为二加入到区间长度为2^(p-1)的的边里面再做下一层次的判断，类似于线段树的lazy标记向下传操作注意，标记下传之后我们还要保证edge这个边标的大小关系，所以，不能直接加到后面，而是用另外一个数组存下传得来的标记（长度短的边标记下传早，所以这个数组自己也是有序的，那么每次取出对应区间最长且长度最短的区间时，我们其实不是直接去edge里面拿而是需要比较这这两个数组还没访问到的的第一个元素的w值，其实也就是类似于两个有序序列的合并操作）。
这样到最后一层，也就是p=0的时候，我们求出来的就是最小生成树了。
本题利用倍增的思想，按照区间从大到小的顺序，每一层做最小生成树，把多余的边早早删掉，实现了算法的优化。

我们来看一个具体的过程：

图片说明