思路为先计算每两个点的距离，然后枚举每个在一个连通块内的点，更新连通块内每个点为起点的最大直径

然后找到连通块内的最大直径

然后找到两个连通块的最小值

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

typedef pair<int,int> pii;

const int N=150;
const double inf=1e20;

int n;
char g[N][N];
pii q[N];
double d[N][N],maxd[N];

double get_dist(pii a,pii b)
{
    double dx=a.first-b.first;
    double dy=a.second-b.second;
    return sqrt(dx*dx+dy*dy);
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>q[i].first>>q[i].second;
    }
    for(int i=0;i<n;i++)
    {
        cin>>g[i];
    }

    //初始化距离
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i!=j)
            {
                if(g[i][j]=='1')
                    d[i][j]=get_dist(q[i],q[j]);
                else
                    d[i][j]=inf;
            }
        }
    }
    //做一遍floyd，计算每两个点之间的距离
    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    //计算maxd，从i开始的最大直径
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(d[i][j]<inf)
            {
                maxd[i]=max(maxd[i],d[i][j]);
            }
        }
    }
    //找到最大直径
    double res1=0;
    for(int i=0;i<n;i++)
    {
        res1=max(res1,maxd[i]);
    }

    double res2=inf;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            //如果两个点不连通,更新一下res2
            if(d[i][j]>=inf)
                res2=min(res2,get_dist(q[i],q[j])+maxd[i]+maxd[j]);
        }
    }
    printf("%lf",max(res1,res2));

    return 0;
}

2023/12/22

复习完课之后做出来了
对floyd求最短路的复习：
最外层代表中间的点

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }

这题需要注意的是，在判断两个点是否连通时，不能根据

if(g[i][j] == '0')

而是要根据:

if(dist[i][j]<INF)

因为要两个点可能最开始不连通，但更新完dist之后是可达的

#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

const int N=160;
const double INF = 1e20;

int n;
// 所有点的坐标
PII q[N];
char g[N][N];
// 两点之间的距离
double dist[N][N];
// maxd[i], 从i出发, 连通块内距离i最远的点
double maxd[N];

double get_dist(PII a,PII b)
{
    double dx=a.first-b.first;
    double dy=a.second-b.second;
    return sqrt(dx*dx+dy*dy);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        q[i]={a,b};
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>g[i][j];
            // 如果为1，则计算两点之间的距离
            if(g[i][j] == '1')
            {
                dist[i][j] = get_dist(q[i], q[j]);
            }
            else
            {
                dist[i][j] = INF;
            }

            if(i == j)
            {
                dist[i][j] = 0;
            }
        }
    }

    // floyd求每个两个点之间的最短路径
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }

    double res1=0;
    // 求每个点到连通块内的最大距离
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            //dist[i][j]<INF 代表i可达j
            if(dist[i][j]<INF)
            {
                maxd[i] = max(maxd[i], dist[i][j]);
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        res1 = max(res1, maxd[i]);
    }

    // 求不连通的两个点，连接起来后直径的最小值
    double res2 = INF;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(dist[i][j]>=INF)
            {
                res2 = min(res2, maxd[i] + maxd[j] + get_dist(q[i], q[j]));
            }
        }
    }

    printf("%lf",max(res1,res2));



    return 0;
}