【例4-2】牛的旅行（信息学奥赛一本通- P1343）-平芜编程栈

【题目描述】

农民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

0. 题目概要

给定N个点的坐标 (N<=150) 和邻接矩阵。图中有若干个不连通的“牧场”（连通块）。

目标：在两个不连通的点(i, j)之间连接一条新边，使得合并后的新牧场直径最小。

输出：这个最小的直径值。

1. 算法解析：

1.1 为什么选 Floyd？

数据范围N<=150，要求任意两点间的距离来判断直径。O(N^3)的 Floyd 算法是最佳选择，代码短且能顺便处理连通性（dis[i][j] == 1e17即不连通）。

1.2 核心：路径拆解

很多同学会陷入误区：每连上一条边后，重新跑一遍Floyd求直径，暴力所有情况，这样复杂度高达 O(N^5)，必超时。

正确思路：利用预处理，O(1)算出连边后的新直径。

一条跨越新边(i, j)的最长路径，一定由三部分组成：

NewPath = 左半区最深 + 桥 + 右半区最深

转化为公式：

len = max_d[i] + dis(i, j) +max_d[j]

其中max_d[i]表示在原连通块内，距离点i最远的点的距离。

1.3 最终答案的陷阱

连接新路后，直径不一定是经过新路的那条。

Ans=max(所有连通块原本的直径, min(经过新桥的直径))

必须取 max，因为修了一座短桥，并不能缩短原本很大的后院。

2. 避坑(学生易错点）

连通块数量陷阱（最易错！）
- 错误想法：认为图里只有 A、B 两个牧场，分别存入两个数组枚举。
- 正解：题目说“至少两个”，可能有 3 个、4 个甚至更多。不要分组，直接双重循环枚举所有 (i, j)，只要g[i][j]==INF就尝试连线。
无穷大的处理
- 本题涉及几何距离 (double)，不能用memset的0x3f。建议定义const double INF = 1e17;。
- floyd 初始化时，g[i][i] = 0，其余为INF。
计算精度
- 使用sqrt(pow...计算两点间距离。
- 判断连通建议写if(g[i][j]<1e16)而不是!= INF，防止精度误差。

3. 完整代码

//150个点用floyd求应该会很好求 #include <iostream> #include <algorithm> #include <cmath> using namespace std; int n;//牧区数 double g[200][200];//邻接矩阵存图 struct node{ double x,y;//牧场横纵坐标 }m[200]; string s; double dis[200]; void floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(g[i][j]>g[i][k]+g[k][j]) g[i][j]=g[i][k]+g[k][j]; } } } } int main(){ cin>>n;//牧区数 for(int i=1;i<=n;i++){//把牧区坐标都存下来 cin>>m[i].x>>m[i].y; } //存图 for(int i=1;i<=n;i++){ cin>>s; for(int j=0;j<n;j++){ g[i][j+1]=s[j]-'0'; } } /* //输出g检查一下 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<g[i][j]<<" "; } cout<<endl; } */ //现在图里有直接边相邻的地方是1，没有边直接连接的地方是0 //这样没法求最短路，我们要初始化0的地方都变成无穷即0x3f3f3f3f //1的地方都变成路径长度 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(g[i][j]==1){//有边直连 g[i][j]=sqrt(pow(m[i].x-m[j].x,2)+pow(m[i].y-m[j].y,2)); } else{//无边直连 g[i][j]=1e17; } } } //然后要初始化每个牧区自己到自己距离为0 for(int i=1;i<=n;i++) g[i][i]=0; //用floyd去求最短路 floyd(); //现在邻接矩阵里已经存了所有连通的最短路 /* //由题目可知，只有两个牧场，所以我们选定任一牧区，该牧区不能抵达的牧区就属于另外一个牧场 //我们就可以把两个牧场内的所有牧区都找到， int a[160];//存放a牧场所有牧区 int b[160];//存放b牧场所有牧区 int ida=0; int idb=0; a[++ida]=1;//将1号牧区先放在a牧场 for(int i=2;i<=n;i++){//遍历所有牧区 if(g[1][i]<1e16) a[++ida]=i;//如果有路放进a牧场 else b[++idb]=i;//否则放进b牧场 } */ double ma=0;//记录几个不连通的牧场情况下 有路的牧区间最远距离 //一个牧场的直径就是牧场中最远的两个牧区的距离 //我们可以求出每个牧场内部，所有牧区到牧场内最远牧区的距离 然后存进dis数组 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ //如果属于同一个牧场(即距离不等于无穷) if(g[i][j]<1e16 && g[i][j]>dis[i]){ dis[i]=g[i][j]; ma=max(ma,g[i][j]);//找出每个牧场内两个距离最远的牧区的距离 } } } //连接起来的新牧场最小直径有两种可能，一种是不经过新链接起来的路，就是在原本各自牧区内部最大距离 //第二种就是必须经过新链接起来的路 那么新最小距离就是两个牧场连接起来的两个点分别去到原 //各自牧场内最远牧区距离再加上新桥的距离 double milen=1e17;//第二种情况下的最短直径 for(int i=1;i<=n;i++){//遍历所有牧区 for(int j=1;j<=n;j++){//遍历所有牧区 //如果i和j间已经有路了或i==j，就跳过 if(g[i][j]<1e16 || i==j) continue; //否则就是没有路，就可以建立路 //先计算出i和j之间路的长度 double len=sqrt(pow(m[i].x-m[j].x,2)+pow(m[i].y-m[j].y,2)); //再加上i在原本牧场内到最远牧区的距离 以及j在原本牧场内到最远牧区的距离 len=len+dis[i]+dis[j]; milen=min(milen,len); } } //原本各自牧场内的直径是不可能因为在两个牧场间加一条路变短的，所以应用ma和milen取最大值 printf("%.6lf",max(ma,milen)); return 0; }