本文共 3028 字，大约阅读时间需要 10 分钟。
Description
农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。这样，农民John就有多个牧区了。
John想在农场里添加一条路径(注意，恰好一条)。对这条路径有以下限制：
一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。考虑如下的有5个牧区的牧场，牧区用“*”表示，路径用直线表示。每一个牧区都有自己的坐标：
这个牧场的直径大约是12.07106, 最远的两个牧区是A和E，它们之间的最短路径是A-B-E。
这里是另一个牧场：
这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。
注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。
输入文件包括牧区、它们各自的坐标，还有一个如下的对称邻接矩阵：
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输入文件至少包括两个不连通的牧区。
请编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。
Input
第1行: 一个整数N (1 <= N <= 150), 表示牧区数
第2到N+1行: 每行两个整数X,Y (0 <= X ,Y<= 100000), 表示N个牧区的坐标。注意每个 牧区的坐标都是不一样的。 第N+2行到第2*N+1行: 每行包括N个数字(0或1) 表示如上文描述的对称邻接矩阵。Output
只有一行，包括一个实数，表示所求答案。数字保留六位小数。
Sample Input
810 1015 1020 1015 1520 1530 1525 1030 100100000010111000010010000100100001110000000000100000010100000010
Sample Output
22.071068
解题思路
不知是我太水了，还是题目太高级了，我就是看不懂题目。后来看了另一版题目，才看懂。。。cao
so，我一定要写题目大意题目大意： 两个牧场，把两个牧场连在一起，求这个大牧场的最大直径，要保证答案是在多种最大直径中最小的。
那么首先想到的,最大直径应该 = = =两个图的最长的那两条直径+把图连接在一起的路径长度。
但是很明显这是不正确的。 A − > B A->B A−>B长度为2； C − > D C->D C−>D长度为8； A = > C A=>C A=>C为最大直径，长度为4（AB为一块，CD为一块）。那么其实原本的小牧场内有更长的直径，自然不能选 A = > C A=>C A=>C这条直径。
#include#include #include #include using namespace std;int n,x[200],y[200];double dis[200][200],v[200];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); memset(dis,0x7f,sizeof(dis)); char c=getchar(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ char c=getchar(); if(c=='1') dis[i][j]=dis[j][i]=sqrt(pow(double(x[i]-x[j]),2)+pow(double(y[i]-y[j]),2)); } char c=getchar(); } //求出每两个牧场的距离 //**************************************************************** //**************************************************************** for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(k!=i&&i!=j&&j!=k) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); //因为保证最小，所以要用最短路求出这个图，用了Floyed //**************************************************************** //**************************************************************** double m=-0x7fffffff; memset(v,-0x7f,sizeof(v)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) if(dis[i][j]!=dis[0][0]) v[i]=max(v[i],dis[i][j]); m=max(m,v[i]); } //求出例子中的“A->B”和“C->D”，m就是“C->D” //**************************************************************** //**************************************************************** double mm=0x7fffffff; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&dis[i][j]==dis[0][0]) mm=min(mm,v[i]+v[j]+sqrt(pow(double(x[i]-x[j]),2)+pow(double(y[i]-y[j]),2))); //求两个板块连在一起的最大直径，例子中的“A->C” //**************************************************************** //**************************************************************** printf("%0.6lf",max(m,mm)); //对比是“C->D”长}
转载地址：http://yqnq.baihongyu.com/