hdu 2874 Connections between cities (添加虚点,并查集+LCA(rmq+dfs))

2016年5月21日 0 作者 CrazyKK

hdu2874题目链接

题意:给一个森林,问两点的最短距离,或者输出两点不联通。

思路:最最重要的一点是:添加虚点!

最最重要的一点是:添加虚点!

最最重要的一点是:添加虚点!

所谓虚点,就是之前假设某个不存在的点,有点类似做辅助线。

通过添加虚点,我们可以把这个森林转化成一棵树。

这样求两点的距离就可以转化成一棵树上的两点的距离。

用dis[u]+dis[v]-2*dis[LCA(u,v)]来求。 dis[i]表示节点i到新的树根节点的距离。

不联通的话就是LCA 为0的情况(0是添加的虚点,作为新的树的根)

具体添加虚点的方法是:森林中每棵树的根连边到虚点上。权值大小随意,因为最后会抵消(?) 为了知道每棵树的根,需要用到并查集(其实根是随便定义的,但是森林中每棵树只能一个点和虚点相连不然就出现环了,所以需要用到并查集)

以及了解了(?)并查集的非递归的路径压缩写法。。。?

缺点是速度更慢,优点是不会爆栈。。。

还有需要学习一下按rank合并和按size合并的进阶并查集。。。?

以及:RE了好多次是因为。。。添加了虚点0,所以各种下标都应该是从0开始,初始化清空的时候忘了(从0开始)清vector…导致多组数据一直往edge[0]里面添加边。。。然后就炸了(手动微笑)