題目

????????農(nóng)民John的農(nóng)場里有很多牧區(qū)，有的路徑連接一些特定的牧區(qū)。

????????一片所有連通的牧區(qū)稱為一個牧場。

????????但是就目前而言，你能看到至少有兩個牧區(qū)不連通。

????????現(xiàn)在，John想在農(nóng)場里添加一條路徑（注意，恰好一條）。

????????一個牧場的直徑就是牧場中最遠的兩個牧區(qū)的距離（本題中所提到的所有距離指的都是最短的距離）。

????????考慮如下的兩個牧場，每一個牧區(qū)都有自己的坐標(biāo)：

????????圖 1 是有 5 個牧區(qū)的牧場，牧區(qū)用“*”表示，路徑用直線表示。

????????圖 1 所示的牧場的直徑大約是 12.07106, 最遠的兩個牧區(qū)是 A 和 E，它們之間的最短路徑是 A-B-E。

????????圖 2 是另一個牧場。

????????這兩個牧場都在John的農(nóng)場上。

????????John將會在兩個牧場中各選一個牧區(qū)，然后用一條路徑連起來，使得連通后這個新的更大的牧場有最小的直徑。

????????注意，如果兩條路徑中途相交，我們不認為它們是連通的。

????????只有兩條路徑在同一個牧區(qū)相交，我們才認為它們是連通的。

????????現(xiàn)在請你編程找出一條連接兩個不同牧場的路徑，使得連上這條路徑后，所有牧場（生成的新牧場和原有牧場）中直徑最大的牧場的直徑盡可能小。

????????輸出這個直徑最小可能值。

輸入格式

????????第 1 行：一個整數(shù) N, 表示牧區(qū)數(shù)；

????????第 2 到 N+1 行：每行兩個整數(shù) X,Y， 表示 N 個牧區(qū)的坐標(biāo)。每個牧區(qū)的坐標(biāo)都是不一樣的。

????????第 N+2 行到第 2*N+1 行：每行包括 N 個數(shù)字 ( 0或1 ) 表示一個對稱鄰接矩陣。

????????例如，題目描述中的兩個牧場的矩陣描述如下：

樣例：A B C D E F G H 
A 0 1 0 0 0 0 0 0 
B 1 0 1 1 1 0 0 0 
C 0 1 0 0 1 0 0 0 
D 0 1 0 0 1 0 0 0 
E 0 1 1 1 0 0 0 0 
F 0 0 0 0 0 0 1 0 
G 0 0 0 0 0 1 0 1 
H 0 0 0 0 0 0 1 0

????????輸入數(shù)據(jù)中至少包括兩個不連通的牧區(qū)。

輸出格式

????????只有一行，包括一個實數(shù)，表示所求答案。

????????數(shù)字保留六位小數(shù)。

數(shù)據(jù)范圍

????????1 ≤ N ≤ 150
????????0≤ X , Y ≤ 10^5

思路

????????1、先將數(shù)據(jù)存儲起來

? ? ? ? 2、初始化點到點的距離

? ? ? ? 3、使用floyd算法算出點到點的最小距離

? ? ? ? 4、保留所有點到點 i 的最大距離，儲存到maxd[]數(shù)組中。

? ? ? ? 5、遍歷maxd[]數(shù)組，距離最大的值就是所有連通圖直徑中的最大值，使用res1儲存。

? ? ? ? 6、遍歷所有點到點的距離，如果距離大于或等于INF則表明這兩個點不在同一個連通圖內(nèi)，將這兩個點連接起來，得到的直徑為maxd[ i ] + maxd[ j ] + get_dist(q[ i ],q[ j ]);如果小于res2則更新res2。

? ? ? ? 7、輸出res1與res2中的最小值。

代碼

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;typedef pair<int,int> PII;const int N = 150;
const double INF = 1e20;int n;// n代表牧區(qū)數(shù)目
PII q[N];// 用來儲存牧區(qū)的坐標(biāo)
char g[N][N];// 用來儲存鄰接矩陣（g[i][j] == '1' 代表點i到點j是連通的，否則代表不連通）
double d[N][N],maxd[N];// d[i][j]代表點i到點j的最小距離，maxd[i]代表所有能到達點i的最小距離中的最大距離double get_dist(PII a,PII b)//求點a到點b的距離
{double dx = a.x - b.x, dy = a.y - b.y;return sqrt(dx * dx + dy * dy);
}int main()
{cin >> n;// 輸入牧區(qū)數(shù)量for(int i = 0; i < n; i ++) cin >> q[i].x >> q[i].y;// 依次輸入牧區(qū)坐標(biāo)for(int i = 0; i < n; i ++) cin >> g[i];// 輸入鄰接矩陣for(int i = 0; i < n; i ++)for(int j = 0; j < n; j ++)if(i != j){if(g[i][j] == '1') d[i][j] = get_dist(q[i],q[j]);// 初始化點i到點j的距離else d[i][j] = INF;}for(int k = 0; k < n; k ++)for(int i = 0; i < n; i ++)for(int j = 0; j < n; j ++)d[i][j] = min(d[i][j],d[i][k] + d[k][j]);// 使用floyd算法求多源匯最短路（任意點到任意點的最短距離）for(int i = 0; i < n; i ++)for(int j = 0; j < n; j ++)if(d[i][j] < INF)maxd[i] = max(maxd[i],d[i][j]);// 求出所有能到達點i的最小距離中的最大距離double res1 = 0;for(int i = 0; i < n; i ++) res1 = max(res1,maxd[i]);// 使用res1儲存所有連通圖中直徑的最大的值double res2 = INF;for(int i = 0; i < n; i ++)for(int j = 0; j < n; j ++)if(d[i][j] >= INF)res2 = min(res2,get_dist(q[i],q[j]) + maxd[i] + maxd[j]);// 使用res2儲存連接一條邊之后所得到新的連通圖的直徑的最小值printf("%lf\n",max(res1,res2));return 0;}

題目來自網(wǎng)站：https://www.acwing.com/