传送门

• 分析:对于给出的邻接矩阵,用并查集维护牧场,并求两点的距离,然后对所有点跑一个floyd(因为只有连通的点我们才求了距离,所以可以直接对所有点跑),对于一个牧场,我们可以求出它里面每个点到其他点的最远距离,以及牧场的直径,那么我们再去枚举任意两个点,如果它们不在一个集合内,那么可以得到这两个点的距离以及这两个点分别到自己牧场某个点的最远距离之和,再去和两个牧场的直径比较一下,维护答案即可.

• 代码:

  #include <bits/stdc++.h>
  #define ll long long
  #define fi first
  #define se second
  #define pb push_back
  #define me memset
  #define rep(a,b,c) for(int a=b;a<=c;++a)
  #define per(a,b,c) for(int a=b;a>=c;--a)
  const int N = 1e6 + 10;
  const int mod = 1e9 + 7;
  const int INF = 0x3f3f3f3f;
  using namespace std;
  typedef pair<int,int> PII;
  typedef pair<ll,ll> PLL;
  ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
  ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
  
  int n;
  pair<double,double> pt[N];
  int p[N];
  int g[200][200];
  double dis[200][200];
  double dp[200][200];
  double len[200];
  double mx_pt[200];
  
  int find(int x){
  	if(p[x]!=x) p[x]=find(p[x]);
  	return p[x];
  }
  
  double get_dis(double x1,double y1,double x2,double y2){
  	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  }
  
  double Min(double x,double y){
  	if(x>y) return y;
  	else return x;
  }
  
  double Max(double x,double y){
  	if(x>y) return x;
  	else return y;
  }
  
  int main() {
      ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  	cin>>n;
  	
  	rep(i,1,n) cin>>pt[i].fi>>pt[i].se;
  	rep(i,1,n) p[i]=i;
  
  	rep(i,1,n){
  		rep(j,1,n){
  			char x;
  			cin>>x;
  			dis[i][j]=1e9;
  			if(x=='1') g[i][j]=1;
  			if(g[i][j]==1 || i==j){
  				dis[i][j]=dis[j][i]=get_dis(pt[i].fi,pt[i].se,pt[j].fi,pt[j].se);
  				int fu=find(i);
  				int fv=find(j);
  				if(fu!=fv){
  					p[fu]=fv;
  				}
  			}
  		}
  	}
  
  	rep(k,1,n){
  		rep(i,1,n){
  			rep(j,1,n){
  				dis[i][j]=Min(dis[i][j],dis[i][k]+dis[k][j]);
  			}
  		}
  	}	
  
  	rep(i,1,n){
  		rep(j,1,n){
  			if(dis[i][j]<1e9){
  				mx_pt[i]=Max(mx_pt[i],dis[i][j]);
  			}
  		}
  		len[find(i)]=Max(len[find(i)],mx_pt[i]);
  	}
  
  	double ans=1e18;
  
  	rep(i,1,n){
  		rep(j,1,n){
  			int fi=find(i);
  			int fj=find(j);
  			if(fi!=fj){
  				double dis_=get_dis(pt[i].fi,pt[i].se,pt[j].fi,pt[j].se);
  				ans=Min(ans,Max(dis_+mx_pt[i]+mx_pt[j],Max(len[fi],len[fj])));
  			}
  		}
  	}
  
  	cout<<fixed<<setprecision(6)<<ans<<'\n';
  
      return 0;
  }