NOIP2013D1T3货车运输题解

NOIP2013D1T3货车运输题解

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

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

步骤：

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

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

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

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

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

注意的地方:

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

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

附代码：

#include<iostream>

#include<climits>

#include<algorithm>

#include<cstdio>

using namespace std;