这是一道纯暴力的题目哦

前言

传送门
这是本蒟蒻第一次发题解，希望大家多多支持！！！

分析

这道题目主要考的不是最短路(~~除了Floyd~~)，关键是对于各个牧区之间的连接和拼接问题。所以，思路首先是要考虑有几个牧场并做好标记（可以利用并查集来实现），其次对于各个牧场中的各个点之间的路进行计算（Floyd），再用一个循环嵌套来便利所有不在同一个牧场的各个牧区（代码中会讲清楚），并算出每种情况下新形成的牧场的直径，再取最小即可。

附加

关于最小值如何取，其他dalao已经说清楚了，我就不再赘述了。。。
以下是借鉴heidoudou大佬的介绍——这里需要比较三个值（牧场 A 的所有最短路的最大值；牧场 B 的所有最短路的最大值，加边后通过这条边的最短路的最大值）

上代码——

#include<bits/stdc++.h> //万能头！！！
using namespace std;
struct node{
	int left,right;
}s[3005]; //结构体的定义（left可以看成x,right可以看成y）
long long n,b,c,be[3005][3005],father[3005]; 
//n如题意,b和c是输入的数字，be用来储存邻接矩阵，father表示并查集中的祖先
char str; //用于邻接矩阵的输入，不然会输入不了
long double ans=1e9,dist[3005][3005],maxx[3005];
//ans储存最后的结果，dist表示两点之间的距离，maxx表示每一个牧场的直径
int find(int x){ /*并查集中的找祖先*/
	if(father[x]!=x) father[x]=find(father[x]);
	return father[x];
}
void add(int x,int y){ /*并查集中的添加关系*/
	father[find(x)]=find(y);
} 
long double leng(int x,int y,int a,int b){ /*两点之间的距离*/
	return sqrt((x-a)*(x-a)+(y-b)*(y-b));
}
int main(){
	cin>>n; //输入
	for(int i=1;i<=n;i++){
		cin>>b>>c;
		s[i].left=b;
		s[i].right=c; //记录每一个点的位置
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>str;
			be[i][j]=str-'0';
        //邻接矩阵的输入及储存方法
		}
	}
	for(int i=1;i<=n;i++){
		father[i]=i;//自己祖先初始化为自己
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(be[i][j]){
				add(i,j);
                dist[i][j]=leng(s[i].left,s[i].right,s[j].left,s[j].right);
                //添加关系以及初始计算两点之间的距离 
			}
			else dist[i][j]=1e9;
            //如果两点之间没有直接关系就将距离设置为一个很大的数（也是Floyd的初始化） 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int w=1;w<=n;w++){
				if(j!=w && find(i)==find(j) && find(j)==find(w)){
					dist[j][w]=min(dist[j][w],dist[j][i]+dist[i][w]);
				}
			}
		}
	}//NB的Floyd算法，计算出再同一个牧场中任意两个点之间的距离 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(find(i)==find(j) && i!=j){
				maxx[find(i)]=max(maxx[find(i)],dist[i][j]);//求出每个牧场的初始直径 
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(find(i)!=find(j)){ /*不在同一个牧场就执行*/ 
				long double ans1=0,ans2=0,l;
                //ans1表示A点现在到距离最远的点的距离,ans2表示的则是B,l表示可能新直径的长度 
				for(int w=1;w<=n;w++){//寻找ans1和ans2的过程 
					if(find(w)==find(i) && i!=w){
						ans1=max(ans1,dist[i][w]);
					}
					if(find(w)==find(j) && j!=w){
						ans2=max(ans2,dist[j][w]);
					}
				}
				l=ans1+ans2+leng(s[i].left,s[i].right,s[j].left,s[j].right);
                //l的赋值 
				ans=min(max(l,max(maxx[find(i)],maxx[find(j)])),ans);
                //在三个可能值中取最小值 
			}
		}
	}
	printf("%.6Lf",ans);//注意要保留小数点后六位，因为用了long double所以要用Lf 
	return 0;//完美的结尾撒花！！！ 
}