题目描述

农民John的农场里有很多牧区，有的路径连接一些特定的牧区。

一片所有连通的牧区称为一个牧场。

但是就目前而言，你能看到至少有两个牧区不连通。

现在，John想在农场里添加一条路径（注意，恰好一条）。

一个牧场的直径就是牧场中最远的两个牧区的距离（本题中所提到的所有距离指的都是最短的距离）。

考虑如下的两个牧场，每一个牧区都有自己的坐标：

1.png

图 1 是有 5 个牧区的牧场，牧区用“*”表示，路径用直线表示。

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

图 2 是另一个牧场。

这两个牧场都在John的农场上。

John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。

注意，如果两条路径中途相交，我们不认为它们是连通的。

只有两条路径在同一个牧区相交，我们才认为它们是连通的。

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

样例

输入样例：
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
难度： 简单
时/空限制： 1s / 64MB
总通过数： 284
总尝试数： 529
来源： 《信息学奥赛一本通》 , usaco training 2.4
算法标签

参考文献

题目的问题：给定两个联通块，在两个连通块中各取任意一点进行连接合成一个连通块，求合并后的联通块的最长路径的最小值

1、各求出两个连通块内部的最长路径的最大值res1

2、任意连接i点和j点，合并成一个连通块，求合并后连通块的且经过i点和j点的最长路径的最小值res2 = min(maxd[i] + get(i,j) + maxd[j])

3、最终合并后连通块的最长路径(直径)的最小值为ans = max(res1,res2);

详细步骤

1、用floyd算法求出任意两点之间的最短距离

2、求maxd[i],表示和i连通的且距离i最远的点的距离

3、

(1)求所有maxd[i]的最大值res1

(2)枚举任意两点i，j连边，满足d[i][j] > INF/2,时 求res2 = min(maxd[i] + get(i,j) + maxd[j])

作者：小呆呆

C++ 代码

//注意本题中的直径的意思并不是直的，而是从某个节点出发到另一个节点的过程中边的权值和最大
//INF 的取值要大于理论距离的最大值为150*1e5*根号2，即所有点都位于对角线上
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define x first
#define y second 
using namespace std;
typedef pair<int,int> PII;
const int N=160,INF=0x3f3f3f3f;
PII q[N];
char g[N][N];
double dist[N][N],maxd[N];//这里的dist数组中的两点间的距离需要自己计算，还需要注意是否联通
int n;
double get_dist(PII a,PII b)
{
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}
int main()
{
    int n;//构建的图一共有n个节点,即编号0-n-1
    cin>>n;

    for(int i=0;i<n;i++)
    cin>>q[i].x>>q[i].y;

    for(int i=0;i<n;i++)
    scanf("%s",g[i]);

    for(int i=0;i<n;i++)//计算dist数组,建图！！！！
    {
        for(int j=0;j<n;j++)
        if(i!=j)
        {
            if(g[i][j]=='1') dist[i][j]=get_dist(q[i],q[j]);//g[i][j]==1代表两点联通，这时就把dist[i][j]计算出来
            else dist[i][j]=INF;
        }
        else dist[i][j]=0;
    }
    //floyd一次可以把i号点到其他点的最短直线距离，下一步把其中的max存到maxd[i]中
    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    double r1=0;//这一步是不考虑加边的情况下找直径
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        if(dist[i][j]<INF/2)//表示i点到j点可以联通，这一步必须判断！！！！！！
        {
            maxd[i]=max(maxd[i],dist[i][j]);
        }
        r1=max(r1,maxd[i]);
    }
    double r2=INF;//这一步考虑在不连通的两个牧区间找连边的方式，让通过新边联通的两点的直线距离最小！！！
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(dist[i][j]>INF/2)//表示这两点不连通，加新边
            r2=min(r2,maxd[i]+maxd[j]+get_dist(q[i],q[j]));
        }

    }
    printf("%.6lf\n",max(r1,r2));
    return 0;
}