QuXiao

每天进步一点点!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  50 随笔 :: 0 文章 :: 27 评论 :: 0 Trackbacks

一个图,有至少2个连通分量,用分别属于不同连通分量的点对将这两个连通分量连接,使其“直径”最小,问最小直径为多少。(直径的定义为连通分量中点对的最短路径中最长的路径)

我的思路是:

1、Floyd算出点对最短路径

2、深搜找出不同连通分量

3、枚举同一连通分量中的点对最短路径,最大的作为该连通分量的直径,顺便算出一点到连通分量中最远点的距离

4、枚举不同连通分量的任意点对a和b,找出以下的最大值

      a所在连通分量的直径
      b所在连通分量的直径
      ab的距离 + a到本连通分量最远距离 + b到本连通分量最远距离

5、找出这些最大值中的最小值

posted on 2011-01-25 22:03 quxiao 阅读(190) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理