1343：【例4-2】牛的旅行——Floyd

【题目描述】
农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，John想在农场里添加一条路径 ( 注意，恰好一条 )。对这条路径有这样的限制：一个牧场的直径就是牧场中最远的两个牧区的距离 ( 本题中所提到的所有距离指的都是最短的距离 )。考虑如下的两个牧场，图１是有5个牧区的牧场，牧区用“*”表示，路径用直线表示。每一个牧区都有自己的坐标：

图１所示的牧场的直径大约是12.07106, 最远的两个牧区是A和E，它们之间的最短路径是A-B-E。

这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。

现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。

【输入】
第 1 行：一个整数N (1 <= N <= 150), 表示牧区数；

第 2 到 N+1 行：每行两个整数X，Y ( 0 <= X，Y<= 100000 )， 表示N个牧区的坐标。每个牧区的坐标都是不一样的。

第 N+2 行到第 2*N+1 行：每行包括N个数字 ( 0或1 ) 表示一个对称邻接矩阵。

例如，题目描述中的两个牧场的矩阵描述如下：

A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
输入数据中至少包括两个不连通的牧区。

【输出】
只有一行，包括一个实数，表示所求答案。数字保留六位小数。

【输入样例】
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
【输出样例】
22.071068

分析

1. 题意：一个牧区就是一个点，一个牧场就是由一些点组成的一个连通块，牧区之间的距离就是两个点之间的距离，牧场的直径是这个牧场所有的点之间 最短距离dis[i][j] 的最大值；由于牧场之间有不连通的，让加入一条边之后，使得新的牧场的所有点之间 最短路 的最大值 最小。
2. 先求所有点之间的最短路dis，再求出每个点i到所有可达的点的最大距离maxdis[i]（maxdis[1]=288.88：说明顶点1到其他可达的n个顶点中的距离最大为288.88），然后求不连通的两个点，假设他们连通后这个新牧场的最大直径minn（calDis(v[i], v[j]) + maxdis[i] + maxdis[j]）；不太理解咋求得这个minn，为啥加个maxdis[i] + maxdis[j]（有知道的大佬评论下）
3. 最后需要和原来未连通的牧场的直径maxdis进行比较，此题是求新牧场的直径（所有的点之间 最短距离的最大值），所以如果maxdis[i]>minn的话，需要替换；
4. 参考：1343：【例4-2】牛的旅行、牛的旅行（信息学奥赛一本通-T1343），勇敢牛牛，不怕旅行

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> P;
const int N = 155, INF = 0x3f3f3f3f;
vector<P> v(N);//存储顶点
double dis[N][N];//存储两点之间的距离(直达的距离)
double maxdis[N];//每个点到所有可达的顶点中的最大值（maxdis[1]=288.88：说明顶点1到其他可达的n个顶点中的距离最大为288.88）
int n;
string s;

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dis[i][j] > dis[i][k] + dis[k][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
            }
        }
    }
}

//两点距离
double calDis(P a, P b) {
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

int main() {
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i].first >> v[i].second;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> s;
        for (int j = 1; j <= s.size(); ++j) {
            if (i == j)
                dis[i][j] = 0;
            else if (s[j - 1] == '1')
                dis[i][j] = dis[j][i] = calDis(v[i], v[j]);
            else
                dis[i][j] = dis[j][i] = INF;
        }
    }
    floyd();

    //求出每个点到所有可达的点的最大距离
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (dis[i][j] < INF && dis[i][j] > maxdis[i])
                maxdis[i] = dis[i][j];
        }
    }

    double minn = INF;//两个不连通的点之间最短距离的（新的连通分量的直径）最小值
    //计算两个连通块，把其中一个连通块每个点到另一个连通块中每个点的距离
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            //找不连通的顶点（也就是不连通的连通块）
            if (dis[i][j] == INF && calDis(v[i], v[j]) + maxdis[i] + maxdis[j] < minn) {
                minn = calDis(v[i], v[j]) + maxdis[i] + maxdis[j];
            }
        }
    }

    //新的大牧场的直径minn不一定比原来的两个牧场大
    for (int i = 1; i <= n; ++i) {
        if (maxdis[i] > minn)
            minn = maxdis[i];
    }
    printf("%.6lf", minn);
    return 0;
}