一個圖,有至少2個連通分量,用分別屬于不同連通分量的點對將這兩個連通分量連接,使其“直徑”最小,問最小直徑為多少。(直徑的定義為連通分量中點對的最短路徑中最長的路徑)
我的思路是:
1、Floyd算出點對最短路徑
2、深搜找出不同連通分量
3、枚舉同一連通分量中的點對最短路徑,最大的作為該連通分量的直徑,順便算出一點到連通分量中最遠點的距離
4、枚舉不同連通分量的任意點對a和b,找出以下的最大值
a所在連通分量的直徑
b所在連通分量的直徑
ab的距離 + a到本連通分量最遠距離 + b到本連通分量最遠距離
5、找出這些最大值中的最小值