洛谷1522 牛的旅行 Cow Tours

题意

给出一个 $N$ 点无向图，至少有两个连通块。求连接两个连通块的方案，使得新连通块的直径最小。

$N\le 150$ 。

题解

先用 $\text{Floyd}$ 跑最短路，然后可以算出从每个点出发的最远距离，然后枚举两个不连通的点连上即可得到答案。

但有可能出现连接的两个点不是直径两端的情况，这时原来连通块的直径就是这个新连通块的直径，所以需要取最大值。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

char ch[155];
int n,x[155],y[155];
double dis[155][155],mx[155];

inline double getDis(int x1,int x2,int y1,int y2) { return sqrt(1.0*((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))); }

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) x[i]=read(),y[i]=read();
    for (int i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        for (int j=1;j<i;j++)
        {
            if (ch[j]=='0') dis[i][j]=dis[j][i]=1e9;
            else dis[i][j]=dis[j][i]=getDis(x[i],x[j],y[i],y[j]);
        }
    }
    for (int k=1;k<=n;k++)
    {
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                if (dis[i][k]+dis[k][j]>=dis[i][j]) continue;
                dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    double ans1=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (dis[i][j]>=1e9) continue;
            mx[i]=max(mx[i],dis[i][j]);
            ans1=max(ans1,mx[i]);
        }
    }
    double ans=1e9;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (dis[i][j]<1e9) continue;
            ans=min(ans,mx[i]+mx[j]+getDis(x[i],x[j],y[i],y[j]));
        }
    }
    return !printf("%.6f",max(ans,ans1));
}