【題目描述】

農(nóng)民John的農(nóng)場里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一片所有連通的牧區(qū)稱為一個牧場。但是就目前而言，你能看到至少有兩個牧區(qū)不連通。現(xiàn)在，John想在農(nóng)場里添加一條路徑 ( 注意，恰好一條 )。對這條路徑有這樣的限制：一個牧場的直徑就是牧場中最遠(yuǎn)的兩個牧區(qū)的距離 ( 本題中所提到的所有距離指的都是最短的距離 )。

考慮如下的兩個牧場，圖１是有5個牧區(qū)的牧場，牧區(qū)用“*”表示，路徑用直線表示。每一個牧區(qū)都有自己的坐標(biāo)：

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

這兩個牧場都在John的農(nóng)場上。John將會在兩個牧場中各選一個牧區(qū)，然后用一條路徑連起來，使得連通后這個新的更大的牧場有最小的直徑。注意，如果兩條路徑中途相交，我們不認(rèn)為它們是連通的。只有兩條路徑在同一個牧區(qū)相交，我們才認(rèn)為它們是連通的。

現(xiàn)在請你編程找出一條連接兩個不同牧場的路徑，使得連上這條路徑后，這個更大的新牧場有最小的直徑。

【輸入】

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

第 2 到 N+1 行：每行兩個整數(shù)X，Y ( 0 ≤ X，Y≤ 100000 )， 表示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ù)。

【輸入樣例】

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

【輸出樣例】

22.071068

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #include<set> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 123 #define E 1e-6 using namespace std; int x[N],y[N]; char s[N]; double g[150+10][150+10],f[150+10]; double calculate(int x1,int y1,int x2,int y2) {return sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2)); } int main() {int n;cin>>n;for(int i=1;i<=n;i++)cin>>x[i]>>y[i];for(int i=1;i<=n;i++){scanf("%s",s+1);for(int j=1;j<=n;j++){if(i!=j){if(s[j]=='0'){g[i][j]=INF;g[i][j]=INF;}else{g[i][j]=calculate(x[i],y[i],x[j],y[j]);g[j][i]=calculate(x[i],y[i],x[j],y[j]);}}elseg[i][j]=0;}}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(g[i][j]>g[i][k]+g[k][j])g[i][j]=g[i][k]+g[k][j];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(g[i][j]<INF&&g[i][j]>f[i])f[i]=g[i][j];double minn=INF;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if( g[i][j]==INF && minn>f[i]+f[j]+calculate(x[i],y[i],x[j],y[j]) )minn=f[i]+f[j]+calculate(x[i],y[i],x[j],y[j]);for(int i=1;i<=n;i++)if(minn<f[i])minn=f[i];printf("%.6lf\n",minn);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛的旅行（信息学奥赛一本通-T1343）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。