题目链接：https://www.luogu.org/problem/P1522
思路：编号，然后跑floyd，这是很清楚的。然后记录每个点在这个联通块中的最远距离。
然后分连通块，枚举两个点（不属于同一个连通块的）建边，计算可能的直径 dist[i] + dist[j] + dis(i,j)。
当然，这里有一个需要注意，（sccno[x]表示属于哪一个编号的连通块，sccdis[x]表示该连通块的直径),
在枚举点建边，形成新的牧场，得到新的可能的直径时，dist[i] + dist[j] + dis(i,j) >= max(sccdis[sccno[i]],sccdis[sccno[j]]),
这个是一定要成立的，因为新的可能的直径不可能小于sccdis[sccno[i]] 和 sccdis[sccno[j]]（结合题目意思）。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
using namespace std; typedef long long LL;
#define inf 1e11
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define rep__(i, j, k) for (int i = (j); i < (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
#define per__(i, j, k) for (int i = (j); i > (k); i--) const int N = ;
int G[N][N];
double f[N][N];
double dist[N];
int sccno[N];
int scccnt;
double sccdis[N];
int scct;
int head[N];
int cnt;
int n; struct node{
double x,y;
}po[N]; struct Edge{
int to;
double w;
int next;
}e[N*N]; void add(int u,int v,double w){
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt++;
} inline double dis(node& a,node& b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} void dfs(int u){
sccno[u] = scccnt;
for(int o = head[u]; ~o; o = e[o].next){
int v = e[o].to;
if(!sccno[v]) dfs(v);
}
} int main(){ scanf("%d",&n); //链式前向星
rep(i,,n) head[i] = -;
cnt = ; //距离矩阵初始化
rep(i,,n) rep(j,,n){
if(i == j) f[i][j] = ;
else f[i][j] = inf;
} //点的输入
rep(i,,n){
scanf("%lf%lf",&po[i].x,&po[i].y);
} //读图
rep(i,,n){
rep(j,,n) scanf("%1d",&G[i][j]);
} //建边
double way;
rep(i,,n) rep(j,i+,n){
if(G[i][j]){
way = dis(po[i],po[j]);
f[j][i] = f[i][j] = way;
add(i,j,way);
add(j,i,way);
}
} //连通图
rep(i,,n) if(!sccno[i]){
++scccnt;
dfs(i);
} //最短路
rep(k,,n) rep(i,,n) rep(j,,n){
f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
} rep(i,,n){
rep(j,,n){
if(f[i][j] == inf) continue;
dist[i] = max(dist[i],f[i][j]);
}
} //连通块最长直径
rep(i,,n){
sccdis[sccno[i]] = max(sccdis[sccno[i]],dist[i]);
} double ans_1 = inf;
double tmp;
rep(i,,n) rep(j,,n){
if(f[i][j] == inf){
tmp = max(sccdis[sccno[i]],sccdis[sccno[j]]);
ans_1 = min(ans_1,dist[i] + dist[j] + dis(po[i],po[j]));
ans_1 = max(ans_1,tmp);
}
} printf("%.6f\n",ans_1); getchar();getchar();
return ;
}