题意：
有 多 个 牧 区 ( 连 通 块 ) ， 每 个 牧 区 的 直 径 为 牧 区 中 相 距 最 远 的 两 点 的 距 离 。 有多个牧区(连通块)，每个牧区的直径为牧区中相距最远的两点的距离。 有多个牧区(连通块)，每个牧区的直径为牧区中相距最远的两点的距离。
这 里 的 距 离 都 是 指 的 两 点 间 的 最 短 距 离 。 这里的距离都是指的两点间的最短距离。 这里的距离都是指的两点间的最短距离。
给 定 一 个 n 个 点 的 图 ， 可 能 有 多 个 连 通 块 。 给定一个n个点的图，可能有多个连通块。 给定一个n个点的图，可能有多个连通块。
要 在 某 两 个 连 通 块 之 间 添 加 一 条 边 ， 使 得 两 个 连 通 块 合 并 为 一 个 连 通 块 。 要在某两个连通块之间添加一条边，使得两个连通块合并为一个连通块。 要在某两个连通块之间添加一条边，使得两个连通块合并为一个连通块。
要 求 合 并 之 后 ， 所 有 连 通 块 中 ， 最 大 直 径 的 最 小 值 。 要求合并之后，所有连通块中，最大直径的最小值。 要求合并之后，所有连通块中，最大直径的最小值。
输入格式
第 1 行：一个整数 N, 表示牧区数；
第 2 到 N+1 行：每行两个整数 X,Y， 表示 N 个牧区的坐标。每个牧区的坐标都是不一样的。
第 N+2 行到第 2*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 ≤ N ≤ 150 , 0 ≤ X , Y ≤ 1 0 5 1≤N≤150, 0≤X,Y≤10^5 1≤N≤150,0≤X,Y≤105
输入样例：
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分析：
对 于 每 个 连 通 块 ， 计 算 直 径 都 得 先 计 算 连 通 块 内 各 点 间 的 最 短 距 离 。 对于每个连通块，计算直径都得先计算连通块内各点间的最短距离。 对于每个连通块，计算直径都得先计算连通块内各点间的最短距离。
所 以 ， 建 图 后 ， 在 每 个 连 通 块 内 部 跑 一 遍 f l o y d 。 所以，建图后，在每个连通块内部跑一遍floyd。 所以，建图后，在每个连通块内部跑一遍floyd。
d i s [ i ] [ j ] 保 存 点 i 和 点 j 之 间 的 最 短 距 离 。 dis[i][j]保存点i和点j之间的最短距离。 dis[i][j]保存点i和点j之间的最短距离。
要 求 所 有 连 通 块 的 最 大 直 径 。 有 两 种 情 况 ： 要求所有连通块的最大直径。有两种情况： 要求所有连通块的最大直径。有两种情况：
① 、 合 并 后 的 连 通 块 的 直 径 不 是 最 大 的 ： ①、合并后的连通块的直径不是最大的： ①、合并后的连通块的直径不是最大的：
最 大 的 直 径 在 原 先 未 合 并 的 几 个 连 通 块 中 取 。 \qquad最大的直径在原先未合并的几个连通块中取。 最大的直径在原先未合并的几个连通块中取。
用 r e s 1 来 更 新 合 并 前 所 有 连 通 块 中 的 最 大 直 径 ， 即 m a x 1 ≤ i , j ≤ n ( d i s [ i ] [ j ] ) 。 \qquad用res1来更新合并前所有连通块中的最大直径，即max_{1≤i,j≤n}(dis[i][j])。 用res1来更新合并前所有连通块中的最大直径，即max1≤i,j≤n(dis[i][j])。
② 、 合 并 后 的 连 通 块 的 直 径 是 最 大 的 ： ②、合并后的连通块的直径是最大的： ②、合并后的连通块的直径是最大的：
假 设 在 点 i 和 点 j 之 间 连 一 条 边 ， 距 离 为 d i s [ i ] [ j ] ， m a x [ i ] 表 示 i 所 在 连 通 块 中 ， 到 i 点 的 最 大 距 离 。 \qquad假设在点i和点j之间连一条边，距离为dis[i][j]，max[i]表示i所在连通块中，到i点的最大距离。 假设在点i和点j之间连一条边，距离为dis[i][j]，max[i]表示i所在连通块中，到i点的最大距离。
则 合 并 后 的 连 通 块 的 直 径 为 m a x [ i ] + d i s [ i ] [ j ] + m a x [ j ] 。 \qquad则合并后的连通块的直径为max[i]+dis[i][j]+max[j]。 则合并后的连通块的直径为max[i]+dis[i][j]+max[j]。
因 此 ， 我 们 还 要 预 处 理 一 个 数 组 m a x [ i ] 。 \qquad因此，我们还要预处理一个数组max[i]。 因此，我们还要预处理一个数组max[i]。
由 于 我 们 要 使 得 最 大 直 径 最 小 ， 因 为 情 况 ① 是 固 定 的 ， 所 以 我 们 要 使 得 情 况 ② 得 到 的 新 的 直 径 尽 量 最 小 。 \qquad由于我们要使得最大直径最小，因为情况①是固定的，所以我们要使得情况②得到的新的直径尽量最小。 由于我们要使得最大直径最小，因为情况①是固定的，所以我们要使得情况②得到的新的直径尽量最小。
用 r e s 2 来 更 新 合 并 后 的 直 径 的 最 小 值 ， 即 m i n 1 ≤ i , j ≤ n ( m a x [ i ] + d i s [ i ] [ j ] + m a x [ j ] ) 。 \qquad用res2来更新合并后的直径的最小值，即min_{1≤i,j≤n}(max[i]+dis[i][j]+max[j])。 用res2来更新合并后的直径的最小值，即min1≤i,j≤n(max[i]+dis[i][j]+max[j])。
最 后 在 r e s 1 和 r e s 2 中 取 一 个 较 大 值 即 可 。 最后在res1和res2中取一个较大值即可。 最后在res1和res2中取一个较大值即可。
注意：
跑 过 f l o y d 后 会 建 立 新 的 连 通 关 系 ， 若 d i s [ i ] [ j ] < i n f 表 示 点 i 和 j 连 通 ， 否 则 表 示 不 连 通 。 跑过floyd后会建立新的连通关系，若dis[i][j]<inf表示点i和j连通，否则表示不连通。 跑过floyd后会建立新的连通关系，若dis[i][j]<inf表示点i和j连通，否则表示不连通。
% l f 默 认 小 数 点 后 保 留 6 位 。 \%lf默认小数点后保留6位。 %lf默认小数点后保留6位。
代码：
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #define P pair<int,int> #define x first #define y second using namespace std; const int N=160; const double inf=1e20; int n; P V[N]; char g[N][N]; double dis[N][N],maxd[N]; double get_dist(P a,P b) { double dx=a.x-b.x,dy=a.y-b.y; return sqrt(dx*dx+dy*dy); } void floyd() { for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } int main() { cin>>n; for(int i=0;i<n;i++) cin>>V[i].x>>V[i].y; 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') dis[i][j]=get_dist(V[i],V[j]); else dis[i][j]=inf; } floyd(); double res1=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) if(dis[i][j]<inf) //连通不能通过g矩阵，因为跑过floyd后可能间接连通 maxd[i]=max(maxd[i],dis[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(dis[i][j]>=inf) res2=min(res2,maxd[i]+get_dist(V[i],V[j])+maxd[j]); printf("%lf\n",max(res1,res2)); return 0; }