牛的旅行

对于这道题,经过分析,我们发现:
对于每一个点,一定会有一个点与他联通且与他的距离最远.
再看一眼n的范围,果断使用Floyd算法.
先求出每一个点到其他点的距离,找出用Maxstep[i]代表与点i相距最远的点距离点i的距离.
先记录一下最大的Maxstep[i],记为ans1.
再考虑加边(注意加边必须加在不连通的两个点之间):
我们枚举每一对不连通的点对,考虑在这两个点加边.
加完边后,我们注意到此时的直径应该是Maxstep[i]+dis(i,j)+Maxstep[j].
我们再找出此时最短的一条Maxstep[i]+dis(i,j)+Maxstep[j],记为ans2.
最终答案记为max(ans1,ans2).

代码

#include <iostream>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N = 160,INF = 0x3f3f3f3f;
int n;
PII q[N];
bool mp[N][N];
double g[N][N],maxd[N];
double get (int a,int b) {
    int dx = q[a].x - q[b].x,dy = q[a].y - q[b].y;
    return sqrt (dx * dx + dy * dy);
}
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> q[i].x >> q[i].y;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            char ch;
            cin >> ch;
            mp[i][j] = ch - '0';
            if (mp[i][j]) g[i][j] = get (i,j);
            else if (i != j) g[i][j] = INF;
        }
    }
    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 ans1 = 0,ans2 = INF;
    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]);
        }
        ans1 = max (ans1,maxd[i]);
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (g[i][j] == INF) ans2 = min (ans2,maxd[i] + get (i,j) + maxd[j]);
        }
    }
    printf ("%.6lf",max (ans1,ans2));
    return 0;
}