[USACO2.4] Cow Tours – Floyd

将二维平面上的一个点称为牧区，牧区之间的距离是通过边的最短路，边是连接某两点的直线，长度定义为欧几里得距离。一个连通块称为牧场。牧场的直径是这个连通块中任选两点的最短路的最大值。现在有两个牧场，你需要建立一条边将它们连通起来，形成一个新的牧场，最小化新牧场的直径。\(N\leq 150\)

Solution

用 Floyd 预处理出两点间最短路后，枚举每个点对 \((i,j) \ s.t. \ i\in A,j\in B\)，然后计算连接 \(i,j\) 时的答案即可

#include <bits/stdc++.h>
using namespace std;

const int N = 155;

int n,c[N];
double g[N][N],ans=1e9,x[N],y[N];
char a[N][N];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++) {
        cin>>a[i]+1;
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(a[i][j]=='1') {
                g[i][j]=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
            }
            else if(i!=j) g[i][j]=1e9;
        }
    }
    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]);
            }
        }
    }
    double tans=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(g[i][j]<1e8) tans=max(tans,g[i][j]);
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(g[i][j]>1e8) {
                double a1=0,a2=0;
                for(int k=1;k<=n;k++) if(g[i][k]<1e8) a1=max(a1,g[i][k]);
                for(int k=1;k<=n;k++) if(g[j][k]<1e8) a2=max(a2,g[j][k]);
                ans=min(ans,a1+a2+sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2)));
            }
        }
    }
    printf("%.6lf",max(tans,ans));
}