首页 > 其他 > 详细

[USACO2004][poj1985]Cow Marathon(2次bfs求树的直径)

时间:2014-03-12 12:55:35      阅读:475      评论:0      收藏:0      [点我收藏+]

http://poj.org/problem?id=1985

题意:就是给你一颗树,求树的直径(即问哪两点之间的距离最长)

分析:

1、树形dp:只要考虑根节点和子节点的关系就可以了

2、两次bfs:

  ①任意从一个点u出发bfs,设其能到的最远点为v

  ②从v出发重新bfs,设其能到达的最远点为s

  ③则树的直径就是v->s

证明:

  若能证明从任意一个点出发,bfs到的最远点一定在树的直径的端点上,那么第二次bfs就可以证明一定正确了,下面来证明第一次bfs正确性:

  ①若选择的点u在直径上,那么能到的最远点v一定是树的直径的端点之一

    反证:

      若v不是树的直径的端点,设树的直径的端点为v1,v2

      那么就说明path(u,v)>path(u,v1),path(u,v)>path(u,v2)

      所以path(v1,u)+path(u,v)>path(v1,v2),这说明v1,v2不是树的直径的端点,与题设不符,故"v不是树的直径的端点"不成立

  ②若选择的点u不在直径上,那么能到的最远点v一定是树的直径的端点之一。这个也很好说明,我们知道树的直径一定是经过根节点的(特殊的根节点如果只有一   个孩子那么就连到根节点为止),即可以理解跨过根节点两边。所以我们在第一次从u bfs的时候,中间一定会bfs到直径上的某点,那么接下来就是又回到了①   情况了。

  综上,成立、

[USACO2004][poj1985]Cow Marathon(2次bfs求树的直径),布布扣,bubuko.com

[USACO2004][poj1985]Cow Marathon(2次bfs求树的直径)

原文:http://www.cnblogs.com/wmrv587/p/3595316.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!