M_sea

洛谷1522 牛的旅行Cow Tours
Luogu算法先使用Floyd算出每两个点的最短距离。然后处理出每一个点能到达的最远的点。然后再枚举加入的一条边,...
扫描右侧二维码阅读全文
26
2018/07

洛谷1522 牛的旅行Cow Tours

Luogu

算法

先使用Floyd算出每两个点的最短距离。

然后处理出每一个点能到达的最远的点。

然后再枚举加入的一条边,找到直径。

最后比较原图的直径和新图的直径,输出较大的。

代码

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

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

inline double get_dis(int X1,int Y1,int X2,int Y2) {
    return sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2));
}

const int MAXN=150+10;
const double INF=0x3f3f3f3f;

double dis[MAXN][MAXN];
double max_dis[MAXN];
int x[MAXN],y[MAXN];

int main() {
    int n=read();
    for (re int i=1;i<=n;i++) x[i]=read(),y[i]=read();
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++) {
            char c=getchar();
            while (c!='0'&&c!='1') c=getchar();
            if (c=='1') dis[i][j]=get_dis(x[i],y[i],x[j],y[j]);
            else if (i!=j) dis[i][j]=INF;
        }

    for (re int k=1;k<=n;k++) //Floyd
        for (re int i=1;i<=n;i++)
            for (re int j=1;j<=n;j++)
                if (dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
    
    double L1=0;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++) {
            if (dis[i][j]!=INF) max_dis[i]=max(max_dis[i],dis[i][j]);
            L1=max(L1,max_dis[i]);
        }
    
    double L2=INF;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++)
            if (dis[i][j]==INF)
            L2=min(L2,max_dis[i]+get_dis(x[i],y[i],x[j],y[j])+max_dis[j]);
    
    printf("%.6f\n",max(L1,L2));
    return 0;
}
最后修改:2018 年 11 月 30 日 10 : 03 PM

发表评论