牛的旅行

题目描述：

n个点，给出每个点的二维坐标，再给出n*n的01关系图，0代表相连，1代表不相连，会形成若干个连通块，规定一个连通块的直径是块中任意两个点的最短距离的最大值，你必须且只能添加一条边，将两个连通块连成一个，问怎么连边能使得剩下的所有块和新生成的块中最大的直径最小，求这个最小值

思路：

我们可以先跑floyed，计算出每个点到每个点的距离，然后开一个数组maxn记录以i为起点能到达的点的最大距离，其实也就是每个块的直径，然后我们枚举两个端点，找不是一个连通块内的两个点，连接起来后生成的直径就是maxn[i] + maxn[j] + x，x是两个点的直线距离，取最小值，然后和maxn[]中的最大值取个max即可

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
#define y1 y114514
int n, m, k;
struct ran{
    double x, y;
}v[200];
char tr[200][200];
double dis[200][200];
double maxn[200];
double getdis(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}


void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> v[i].x >> v[i].y;
    }
    for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)dis[i][j] = (i == j ? 0.0 : 1000000000.0);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> tr[i][j];
            if(tr[i][j] == '1'){
                dis[i][j] = getdis(v[i].x, v[i].y, v[j].x, v[j].y);
            }
        }
    }
    for(int k = 1; k <= n; ++k){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    double ans1 = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(dis[i][j] > 10000000)continue;
            else maxn[i] = max(maxn[i], dis[i][j]);
        }
        ans1 = max(ans1, maxn[i]);
    }
    double ans2 = 10000000;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(dis[i][j] > 10000000){
                ans2 = min(ans2, maxn[i] + maxn[j] + getdis(v[i].x, v[i].y, v[j].x, v[j].y));
            }
        }
    }
    printf("%.6f", max(ans1, ans2));
}


int main(){
    io;
    work();
    return 0;
}