跳至正文
题库4018
#4018

1343. 【例4-2】牛的旅行

查看题目操作

1343. 【例4-2】牛的旅行

题目描述

每个牧区有一个平面坐标,已有道路连接部分牧区;道路长度等于两端坐标的欧氏距离,双向通行。每个连通分量称为一个牧场,其直径是分量内任意两点最短距离的最大值。至少有两个牧场,现在恰好添加一条连接不同牧场的道路,使添加后全农场各连通牧场直径的最大值最小;原有的其他牧场直径也必须计入。道路在中途相交不产生连接。
样例牧区坐标
结点xy
A1010
B1510
C2010
D1515
E2015
F3015
G2510
H3010
样例已有道路为 A-B、B-C、B-D、B-E、C-E、D-E、F-G、G-H。第一片牧场直径为 A-B-E 的 12.071068;新增 C-G 后全农场最大直径为 22.071068。

输入格式

第 1 行:一个整数N (2 ≤ N ≤ 150), 表示牧区数; 第 2 到 N+1 行:每行两个整数X,Y ( 0 ≤ X,Y≤ 100000 ), 表示N个牧区的坐标。每个牧区的坐标都是不一样的。 第 N+2 行到第 2*N+1 行:每行包括N个数字 ( 0或1 ) 表示一个对称邻接矩阵;每行是一个不含空格的 N 位01串,对角线为0。 例如,题目描述中的两个牧场的矩阵描述如下:
 
样例邻接矩阵
ABCDEFGH
A01000000
B10111000
C01001000
D01001000
E01110000
F00000010
G00000101
H00000010
输入数据中至少包括两个不连通的牧区。

输出格式

只有一行,包括一个实数,表示所求答案。数字保留六位小数。允许绝对误差1e-6或相对误差1e-9,不得输出额外内容。
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

来源

一本通在线评测 ybtbas-1343