洛谷P1522 [USACO2.4]牛的旅行 Cow Tours 题解

题目链接：P1522 [USACO2.4]牛的旅行 Cow Tours

题意：给定一张无向图，有至少 2 2 2 个连通分量，定义直径为每个连通分量中任意两结点的最短路径的最大值，其中相邻结点边权为它们的欧几里德距离，现在要求添加一条边使得连通分量的数量减少 1 1 1 ，并使得这个新连通分量的直径尽可能地小，求这个最小值

题意已经简化过了 应该很好懂

由于 N ≤ 150 N\le 150 N≤150 显然我们可以用 Floyd 来求这个最短路径

任意两个连通块 A , B A,B A,B 连边，可能出现以下三种情况

1. A A A 的直径最大
2. B B B 的直径最大
3. A A A 和 B B B 相连后的新直径最大，即 w ( i , j ) + d ( i ) + d ( j ) w(i,j) + d(i) + d(j) w(i,j)+d(i)+d(j) ， 其中 d ( i ) d(i) d(i) 指从结点 i i i 出发的最长路径的长度

那我们求一下就好了 qwq 就这么简单

注意这个最大值不能在Floyd的时候更新，因为那个时候还不是最短路径…

时间复杂度 O ( n 3 ) O(n^3) O(n3)

代码如下（无视我的垃圾卡常）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(255)
#define INF 1e18+5
#define Max(a,b) a=fmax(a,b)
#define Min(a,b) a=fmin(a,b)
#define max3(a,b,c) fmax(a,fmax(b,c))
int n;
char s[MAXN];
int x[MAXN],y[MAXN],f[MAXN];
double ans=INF,fmx[MAXN],pmx[MAXN],g[MAXN][MAXN],A,B,C;
double dis(int i,int j)
{return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}
void init(){for(int i=1; i<=n; i++) f[i]=i;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int u,int v){f[find(u)]=find(v);}
signed main()
{
    scanf("%lld",&n);
    for(int i=1; i<=n; i++)
        scanf("%lld%lld",&x[i],&y[i]);
    init();for(int i=1; i<=n; i++)
    {
        scanf("%s",s+1);
        for(int j=1; j<=n; j++)
            if(s[j]=='1')
            {
                merge(i,j);
                g[i][j]=dis(i,j);
            }else g[i][j]=(i!=j)?INF:0;
    }
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            if(g[i][k]!=INF)
            for(int j=1; j<=n; j++)
                Min(g[i][j],g[i][k]+g[k][j]);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            if(g[i][j]<INF)
                Max(pmx[i],g[i][j]);
        Max(fmx[find(i)],pmx[i]);
    }
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            if(find(i)!=find(j))
            {
                A=fmx[find(i)],B=fmx[find(j)];
                C=pmx[i]+pmx[j]+dis(i,j);
                Min(ans,max3(A,B,C));
            }
    printf("%.6lf",ans);
    return 0;
}

转载请说明出处