NOIP2013D1T3货车运输题解

作者:薛琛    发布时间:2017/3/30    浏览:433

NOIP2013D1T3货车运输题解

题目见:https://www.luogu.org/problem/show?pid=1967

此题用的是kruskal求最大生成森林,然后倍增LCA求最小值(其实也可以不用求lca

步骤:

1.读入,按边的长度排序

2.kruskal的经典做法,只不过是从大到小把边加入,每条边都遍历一遍,这样生成的就不一定是一棵树而可能是一片森林

3.对于读入的每个询问,并查集判断是否在同一个集合,如果不在则走不到,答案记录为-1(并查集早在kruskal的时候就做好了对吧)

4.遍历每个点,为根节点的则建树,把深度什么的一遍dfs全搞定吧,同时在这个时候还可以记录每个点与父节点的边的编号

5.再次枚举每个询问,已经为-1的跳过,剩下的只要求路径上最短的边就好,树上ST,当做RMQ来做什么的真的很没必要,完全可以一步步往上爬。假设要从xyplca(x,y),则分别从xy往上爬到p为止,记录最小的那条边即是答案.

注意的地方:

1.知道kruskal的都清楚kruskal的边存储方式,但这种存储方式在后面的深搜建树中很不好用(因为每一次找连接的点都要遍历所有边一次,妥妥的超时),所以在kruskal的时候还要重建一次邻接表存储的边方便建树..

2.可以不用倍增求LCA,不知道怎么求lca的同学们就用最基本的方法好了。对于要求的xy来说(假设d[x]>d[y]d为深度),先让x一步步往上爬到深度跟y相等,在这个过程中也存下最短边,与后面比较。深度相同之后,xy一起一步步往上爬到各自的父节点,中途记录最短边,直到xy相等,这样做也并不会超时.

附代码:

#include<iostream>

#include<climits>

#include<algorithm>

#include<cstdio>

using namespace std;

 

Copyright@2009-2018 株洲市南方中学 All Rights Reserved

湘公网安备 43020302000273号

湘ICP备18002763号-1  湘教QS7-200505-000292   投稿入口 校内办公入口

株洲市南方中学 学校地址:株洲市芦淞区董家塅

招生热线

0731-28550326

28552555