描述

農(nóng)民John的農(nóng)場里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一片所有連通的牧區(qū)稱為一個牧場。但是就目前而言，你能看到至少有兩個牧區(qū)通過任何路徑都不連通。這樣，農(nóng)民John就有多個牧場了。?

John想在農(nóng)場里添加一條路徑(注意，恰好一條)。對這條路徑有以下限制：?

一個牧場的直徑就是牧場中最遠的兩個牧區(qū)的距離(本題中所提到的所有距離指的都是最短的距離)。考慮如下的有5個牧區(qū)的牧場，牧區(qū)用“*”表示，路徑用直線表示。每一個牧區(qū)都有自己的坐標：?

???????????????15,15???20,15
?????????????????D???????E
?????????????????*-------*
?????????????????|?????_/|
?????????????????|???_/??|
?????????????????|?_/????|
?????????????????|/??????|
????????*--------*-------*
????????A????????B???????C
????????10,10???15,10???20,10
這個牧場的直徑大約是12.07106,?最遠的兩個牧區(qū)是A和E，它們之間的最短路徑是A-B-E。?

這里是另一個牧場：?

?????????????????????????*F?30,15
????????????????????????/?
??????????????????????_/??
????????????????????_/????
???????????????????/??????
??????????????????*------*?
??????????????????G??????H
??????????????????25,10???30,10
這兩個牧場都在John的農(nóng)場上。John將會在兩個牧場中各選一個牧區(qū)，然后用一條路徑連起來，使得連通后這個新的更大的牧場有最小的直徑。?

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

輸入文件包括牧區(qū)、它們各自的坐標，還有一個如下的對稱鄰接矩陣：?

　　?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
輸入文件至少包括兩個不連通的牧區(qū)。?

請編程找出一條連接兩個不同牧場的路徑，使得連上這條路徑后，這個更大的新牧場有最小的直徑。?
?

輸入格式

第1行:?一個整數(shù)N?(1?<=?N?<=?150),?表示牧區(qū)數(shù)?

第2到N+1行:?每行兩個整數(shù)X,Y?(0?<=?X?,Y<=?100000),?表示N個牧區(qū)的坐標。注意每個?牧區(qū)的坐標都是不一樣的。?

第N+2行到第2*N+1行:?每行包括N個數(shù)字(0或1)?表示如上文描述的對稱鄰接矩陣。?
?

輸出格式

只有一行，包括一個實數(shù)，表示所求直徑。數(shù)字保留六位小數(shù)。?

測試樣例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

輸出

22.071068

備注

USACO?2.4.3

轉(zhuǎn)載于:https://www.cnblogs.com/radiumlrb/p/5799578.html

總結(jié)

以上是生活随笔為你收集整理的TYVJ P1069 cowtour 看不懂题意的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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