题目：https://www.luogu.org/problemnew/show/P1522
懒于仔细分情况而直接像题解那样写floyd然后不明白最后一步max的含义了...
分开考虑怎么保证在一个内呢？如果新连边的min与原直径的max在三个连通块里怎么办？
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; double const inf=0x3f3f3f3f; int n,xx[155],yy[155],col[155],cr; double dis[155][155],ans,mx[155],as,s[155]; double cal(int i,int j) { return sqrt(1.0*(xx[i]-xx[j])*(xx[i]-xx[j])+1.0*(yy[i]-yy[j])*(yy[i]-yy[j])); } //void dfs(int x) //{ // col[x]=cr; // for(int i=1;i<=n;i++) // if(i!=x&&dis[i][x]!=inf&&!col[i])dfs(i); //} int main() { scanf("%d",&n); ans=inf; for(int i=1;i<=n;i++) scanf("%d%d",&xx[i],&yy[i]); int d; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%1d",&d);// if(d==1)dis[i][j]=cal(i,j); else if(i!=j)dis[i][j]=inf; } // for(int i=1;i<=n;i++) // if(!col[i])cr++,dfs(i); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(dis[i][j]!=inf) { mx[i]=max(mx[i],dis[i][j]); as=max(as,dis[i][j]); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(dis[i][j]==inf)ans=min(ans,mx[i]+mx[j]+cal(i,j)); printf("%.6lf",max(ans,as)); return 0; }
原文：https://www.cnblogs.com/Zinn/p/8954462.html