一个图,有至少2个连通分量,用分别属于不同连通分量的点对将这两个连通分量连接,使其“直径”最小,问最小直径为多少。(直径的定义为连通分量中点对的最短路径中最长的路径)
我的思路是:
1、Floyd算出点对最短路径
2、深搜找出不同连通分量
3、枚举同一连通分量中的点对最短路径,最大的作为该连通分量的直径,顺便算出一点到连通分量中最远点的距离
4、枚举不同连通分量的任意点对a和b,找出以下的最大值
a所在连通分量的直径
b所在连通分量的直径
ab的距离 + a到本连通分量最远距离 + b到本连通分量最远距离
5、找出这些最大值中的最小值