【洛谷P1522】牛的旅行

题目大意：给定一个 N 个顶点的无向图，图中有若干联通块，现定义联通块的直径为该联通块中距离最远的两个点的距离，定义无向图的直径为这个图中所有联通块直径的最大值。现在在图上加一条边，使得两个本不连通的联通块得以联通，求加入一条边之后整张图直径的最大值最小是多少。

题解：首先在不加入边的情况下，图的直径为所有联通块直径的最大值。在加入某一条边时，可能对答案做贡献的情况即经过该边的一条穿过两个联通块的路径，显然，这个路径的值等于加入边的权值+该边的两个端点到各自联通块中距离的最大值。因此，需要预处理出每个点到各自联通块中点距离的最大值，这个问题又可以归约为多源最短路问题，即：Floyd。

通过这道题也学到了 floyd 的另一个性质，即：跑完 floyd 之后，若两点距离还是无穷，则证明这两个点不连通，利用这个性质即可完成联通块内的枚举。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=150+10;

const double inf=1e15;

double x[maxn],y[maxn],d[maxn][maxn],mxdis[maxn],len;

int n;

inline double calc(int i,int j){

    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

}

void read_and_parse(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++){

            int dis;

            scanf("%1d",&dis);//表示读取缓冲区中一个字符，性能比字符串读取差

            if(dis)d[i][j]=calc(i,j);

            else if(i!=j)d[i][j]=inf;

        }

}

void floyd(){

    for(int k=1;k<=n;k++)

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

}

void solve(){

    floyd();

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++){

            if(d[i][j]==inf)continue;

            mxdis[i]=max(mxdis[i],d[i][j]);

            len=max(mxdis[i],len);

        }

    double len2=inf;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            if(d[i][j]==inf)

                len2=min(len2,mxdis[i]+calc(i,j)+mxdis[j]);

    printf("%.6lf\n",max(len,len2));

}

int main(){

    read_and_parse();

    solve();

    return 0;

}