题目描述
Farmer John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，John想在农场里添加一条路径（注意，恰好一条）。对这条路径有这样的限制：一个牧场的直径就是牧场中最远的两个牧区的距离（本题所提到的所有距离指的都是最短的距离）。考虑如下的两个牧场，图中是具有5个牧区的牧场，牧区用星号表示，路径用直线表示，每一个牧区都有自己的坐标：
图中所示的牧场的直径大约是12.07106，最远的两个牧区是A和E，它们之间的最短路径是A-B-E。
这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。
现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的路径。
输入输出格式
输入格式
第一行，一个整数n（1≤n≤150），表示牧区数；
第二至第n+1行，每行两个整数x，y（0≤x，y≤100000），表示n个牧区的坐标，每个牧区的坐标都是不一样的。
第n+2至第2n+1行，每行包括n个数字（0或1），图示一个对称邻接矩阵。
例如，题目描述中的两个牧场的矩阵描述如下：
输入数据中至少包括两个不连通的牧区。
输出格式
只有一行，包括一个实数，表示所求答案。数字保留六位小数。
输入输出样例
输入样例
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
题解
主要思路就是用并查集求牧场。然后用floyd求出同一牧场中的任意两点之间的最短路，再求出牧场中任意结点到其它结点的最长路径和这个牧场的直径，根据这些信息枚举连接两点建边形成新牧场并求出其路径。
注意新牧场的直径可能是原来牧场的直径，因为可能有大牧场包小牧场，新边连接直径中间等特殊情况。
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define MAX_N 150 #define INF 100000000000000.0f #define Max(x, y) (x >= y ? x : y) #define Min(x, y) (x <= y ? x : y) #define Abs(x) (x >= 0 ? x : -x) #define Dis(a, b) sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b])) using namespace std; int n; double x[MAX_N | 1], y[MAX_N | 1]; double d[MAX_N | 1][MAX_N | 1]; double maxd[MAX_N | 1]; double maxmd[MAX_N | 1]; int r[MAX_N | 1]; double ans = INF; inline int Root(int x) { int R = x, tmp; while(R != r[R]) R = r[R]; while(x != r[x]) tmp = r[x], r[x] = R, x = tmp; return R; } int main() { scanf("%d", &n); for(register int i = 1; i <= n; ++i) { scanf("%lf%lf", &x[i], &y[i]); } for(register int i = 1; i <= n; ++i) { r[i] = i; } for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= n; ++j) { d[i][j] = INF; } } int tmp; for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= n; ++j) { scanf("%1d", &tmp); if(tmp) { d[i][j] = Dis(i, j); if(Root(i) != Root(j)) r[Root(i)] = Root(j); } } } for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= n; ++j) { if(i != j && Root(i) != Root(j)) { d[i][j] = Dis(i, j); } } } for(register int k = 1; k <= n; ++k) { for(register int i = 1; i <= n; ++i) { if(i == k || Root(i) != Root(k)) continue; for(register int j = 1; j <= n; ++j) { if(i == j || j == k || Root(i) != Root(j)) continue; d[i][j] = Min(d[i][j], d[i][k] + d[k][j]); } } } for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= n; ++j) { if(i == j || Root(i) != Root(j)) continue; maxd[i] = Max(maxd[i], d[i][j]); } maxmd[Root(i)] = Max(maxmd[Root(i)], maxd[i]); } for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= n; ++j) { if(i == j || Root(i) == Root(j)) continue; ans = Min(ans, Max(Max(maxmd[Root(i)], maxmd[Root(j)]), maxd[i] + maxd[j] + Dis(i, j))); } } printf("%.6lf", ans); return 0; }