poj 1985 Cow Marathon (树的直径模板题)

poj1985
题意:求树上两点的最长距离。。。也就是传说中的树的直径。。。

思路: 两遍BFS :先任选一个起点BFS找到最长路的终点,再从终点进行BFS,则第二次BFS找到的最长路即为树的直径;
原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点
证明: 1) 如果u 是直径上的点,则v显然是直径的终点(因为如果v不是的话,则必定存在另一个点w使得u到w的距离更长,则于BFS找到了v矛盾)
2) 如果u不是直径上的点,则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了
所以v一定是直径的一个端点,所以从v进行BFS得到的一定是直径长度

 

参考博客

 

实际写的时候,第一次bfs最后一个出队的点就是直径的一个端点。。。

好像错了。。。还是稳妥一点。。。最后扫一遍。。距离最远的一定是端点。。。
然后因为题目没有数据范围。。。?re多次orz。。。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz