题目：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; }
