P1522 [USACO2.4]牛的旅行 Cow Tours

图被划分成两块连通块，现用一条边将两块连通块连接起来，使得图的直径（最远的两个点的最短距离）最小

1. 既然要求最短路径，观察数据范围，采用Floyd算法求得任意两点间最短路径
2. 然后枚举所有不连通的两点，判断以当前两点间的距离为边将连通块连通得到的图的直径是否最小（在此之前要预处理出每个点在连通块内所能抵达的最远距离）
3. 注意图的直径不一定横跨两个连通块，有可能存在某一连通块内部
4. 对\(2,3\)两种情况取较大者即可

const int N=155;
double g[N][N];
PII a[N];
double maxd[N];
int n;

double dis(PII a,PII b)
{
    return sqrt((a.fi-b.fi)*(a.fi-b.fi)+(a.se-b.se)*(a.se-b.se));
}

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

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i].fi>>a[i].se;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            char c;
            cin>>c;
            g[i][j]=c-‘0‘;
            if(g[i][j] == 1) g[i][j]=dis(a[i],a[j]);
            if(i!=j && !g[i][j]) g[i][j]=INF;
        }

    floyd();

    double res1=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(g[i][j] != INF) maxd[i]=max(maxd[i],g[i][j]);
            res1=max(res1,maxd[i]);
        }

    double res2=INF;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(g[i][j] == INF)
                res2=min(res2,maxd[i]+maxd[j]+dis(a[i],a[j]));

    printf("%f\n",max(res1,res2));
    //system("pause");
}

P1522 [USACO2.4]牛的旅行 Cow Tours

原文：https://www.cnblogs.com/fxh0707/p/13629603.html