111qqz的小窝

老年咸鱼冲锋!

hdu 2586 How far away ? (tarjan算法求LCA模板题)

题目链接
题意:一棵树,给出n-1个边权,然后q组查询,每组查询询问两个点之间的距离。
思路:

dfs跑出根到每个点的距离,设为dis[i]
那么u,v两点的距离就是ans = dis[u]+dis[v]-2*dis[lca(u,v)];

其中lca(u,v)为u,v的最近公共祖先。 这个式子是利用容斥,其实也很直观。。不理解的话画个图就好。

所以终点就是求两个点的LCA.

据说有好多种做法。今天学习了大概是最简单的一种?
学习链接

 

我的理解:其实本质就是利用并查集。。在访问一个点的子树的时候,这个点其所有子树的祖先。。。由于祖先的节点比较小,所以merge的时候要f[大]=小…

要注意Tarjan 算法是离线算法。

哦对了。。这题要扩展语句才能过,不然会RE…

 

 

codeforces 567 E President and Roads (优先队列+迪杰斯特拉+tarjan)

题意是说,给定一个有向图,对于每一条边,问是否是s到t的最短路上一定会经过的边.

如果是就输出yes

如果不是,问能否通过减少这条边的权值(减少的权值就是修理费用),使得这条边成为新的最短路上的边.

对于一条边是否一定是最短路上的边,我们可以从s做一遍最短路,然后反响建边,从t再做一遍最短路.

得到两个d1,d2数组

如果一条边d1[u] + d2[v] + w(u, v) = 最短路,那这条边在最短路上的边.但是未必不能缺少.

我们还要判断这条边是否是不能缺少的.

不能缺少的意思是说,如果没有这条边,就不能构成最短路.

那么这条边一定是桥.

我们可以用tarjan算法求桥.

 

据说是水题,不过图论还没怎么刷,所以对我来说还是很有难度的.

只是基本懂了

下面的代码是我仿照其他人的代码写出来的….求不鄙视 ><