題目描述

牛的旅行

農民John的農場里有很多牧區。有的路徑連接一些特定的牧區。一片所有連通的牧區稱為一個牧場。但是就目前而言，你能看到至少有兩個牧區不連通。

現在，John想在農場里添加一條路徑 ( 注意，恰好一條 )。對這條路徑有這樣的限制：一個牧場的直徑就是牧場中最遠的兩個牧區的距離 ( 本題中所提到的所有距離指的都是最短的距離 )。

考慮如下的兩個牧場，圖１是有$5$個牧區的牧場，牧區用*表示，路徑用直線表示。每一個牧區都有自己的坐標：

圖１所示的牧場的直徑大約是$12.07106$, 最遠的兩個牧區是$A$和$E$，它們之間的最短路徑是$A\to B\to E$。 這兩個牧場都在John的農場上。John將會在兩個牧場中各選一個牧區，然后用一條路徑連起來，使得連通后這個新的更大的牧場有最小的直徑。

注意，如果兩條路徑中途相交，我們不認為它們是連通的。只有兩條路徑在同一個牧區相交，我們才認為它們是連通的。

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

輸入格式

第 1 行：一個整數$N$ ($1\le N\le 150$), 表示牧區數；
第 2 到 $N+1$ 行：每行兩個整數$X$，$Y$ ( $0\le X，Y\le 100000$ )， 表示$N$個牧區的坐標，每個牧區的坐標都是不一樣的。
第 $N+2$ 行到第 $2\times N+1$ 行：每行包括$N$個數字 ( $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

輸出格式

只有一行，包括一個實數，表示所求答案。數字保留六位小數。

樣例 #1

樣例輸入 #1

8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010

樣例輸出 #1

22.071068

算法思想

根據題目描述，測試樣例可以得到這樣一張圖：

其中$A,B,C,D,E$屬于一個牧場，$F,G,H$屬于另外一個牧場。現在要將兩個牧場用一條路徑連起來，使得連通后這個新的更大的牧場有最小的直徑。

用一條路徑連接后，要求所有牧場（生成的新牧場和原有牧場）中直徑最大的牧場，使其直徑盡可能小。那么直徑最大的牧場無非有兩種情況：

• 最大牧場是原有牧場
• 最大牧場是生成的新牧場

可以確定結果一定是大于等于所有原有牧場的直徑的，并且生成的新牧場的直徑必須盡可能的小，所以答案應該取這兩者的最大值。

那么算法的基本思想：

• 首先求出原有牧場中，任意兩個的牧區之間的最短距離，可以用「Floyd」算法完成
• 然后求出在同一牧場中，到牧區$i$的最遠距離$maxd[i]$，同時打擂臺求其中的最大值$res1$，就是原有牧場的直徑最大值。
• 其次，枚舉一條連接兩個不同牧場的路徑，求出連接后的牧場直徑，即$maxd[i]+x+maxd[j]$，其中$i$和$j$屬于不同牧場，$x$表示牧區$i$和$j$的距離，那么其中最小的就是生成的新牧場的直徑$res2$。
• 最后，$res1$和$res2$的最大值就是答案。

時間復雜度

本題的核心是使用Floyd算法計算任意兩個牧區之間的最短路，時間復雜度為$O(n^3)$。

代碼實現

#include <bits/stdc++.h>
using namespace std;
typedef pair<double,double> PDD;
const int N = 155;
const double INF = 1e20;
int n;
PDD p[N];
char g[N][N];
double d[N][N], maxd[N]; //maxd[i]表示在一個牧場中距離牧區i的最遠距離
double get_dis(PDD a, PDD b)
{double dx = a.first - b.first;double dy = a.second - b.second;return sqrt(dx * dx + dy * dy);
}
int main()
{cin >> n;for(int i = 0; i < n; i ++) cin >> p[i].first >> p[i].second;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) d[i][j] = 0; //同一個點else if(g[i][j] == '1') d[i][j] = get_dis(p[i], p[j]); //相鄰計算距離else d[i][j] = INF;//Floyd計算任意兩點之間的距離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]);double res1 = 0;//計算每個牧區連通的最遠牧區的距離for(int i = 0; i < n; i ++){for(int j = 0; j < n; j ++){if(d[i][j] < INF / 2) //i和j是連通的maxd[i] = max(maxd[i], d[i][j]);}res1 = max(res1, maxd[i]); //求所有牧場的最大直徑}//枚舉一條連接兩個不同牧場的路徑double res2 = INF; //求連通兩個牧場后，直徑的最小值for(int i = 0; i < n; i ++)for(int j = 0 ; j < n; j ++){if(d[i][j] > INF / 2) //兩個牧區不連通{double x = get_dis(p[i], p[j]);res2 = min(res2, maxd[i] + x + maxd[j]);}}printf("%.6lf", max(res1, res2));return 0;
}