Frog

Description
有一只叫做Freddy的青蛙坐在湖中央的一块石头上，突然间他发现另一只青蛙（她的名字是Fiona）坐在另一颗石头上。他想要过去找她，但是因为湖水很脏，到处充满着游客的防晒油，所以他决定用跳的，而不要用游的。
不妙的是Fiona的石头离他的距离超出他所能跳的范围。因此Freddy考虑利用其它的一些石头当作中继站，因此他就可以跳比较小的距离（或许要跳许多次）去找Fiona。
要这样子连续的跳，很明显的Freddy一次能跳的距离必须至少和这一串石头间的距离最大的距离一样。因此，介于石头间的蛙跳距离（frog distance，人类也称之为minmax distance）定义为要从Freddy所在的石头要跳到Fiona所在的石头的路径中，最小必须要跳的距离。
给你Freddy所在的石头、Fiona所在的石头，以及湖中所有其它石头的坐标，你的任务是算出介于Freddy和Fiona所在石头间的蛙跳距离。
Input
输入含有多组测试数据。每组测试资料的第一列有1个整数n，代表石头的数目（2 <= n <= 200）。接下来的n列每列有2个整数xi，yi（0 <= xi，yi <= 1000）代表第i颗石头的坐标。其中第一颗为Freddy所在的石头，第二颗为Fiona所在的石头，其它的n-2颗石头上则是空的。
每组测试数据后有一空白列，当n=0时代表输入结束。请参考Sample Input。
Output
对每一组测试数据，输出一列这是第几组测试数据，以及一列蛙跳距离。
每组测试数据后亦输出一空白列。请参考Sample Output。
Sample Input
2
0 0
3 4

3
17 4
19 4
18 5

0
Sample Output
Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414

sol：

问题归纳：找出发点到结束点路径上的最大边权值最小，输出该值。如下图，出发点1，结束点5。1到5有多条路径，但1-3-2-1这条路径上的最大边权值为6，在所有路径中是最小的。

解决方法：先将边权按从小打到大排序，排序后依次加边，放入集合，每加一条边，判断起始点和结束点是否已在一个集合中。若在，则说明起始点与结束点已连通，当前的边权值为答案。如上图，先加2-5，边权为1，再加1-3，边权为3，再加2-3，边权为4，再加1-3，边权为6，此时起点1与终点5已连通，此时的6即为答案。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,c,qaq;
double a[2010],b[2010],ans;
struct kkk{
    int x,y;double v;
}bb[1000000];int tot;
bool cmp(kkk a,kkk b)
{return a.v<b.v;}
int fa[2010];
int get(int x){return fa[x]==x?fa[x]:fa[x]=get(fa[x]);}
double turn(int x,int y) 
{
    double dx = a[x] - a[y];
    double dy = b[x] - b[y];
    return sqrt(dx * dx + dy * dy);
}
int main()
{
    while(1)
    {
        ++qaq;
        scanf("%d",&n);
        if(n==0) break;
        tot=0;
        for(int i=1;i<=n;i++)
        fa[i]=i;
        for(int i=1;i<=n;i++)
        scanf("%lf %lf",&a[i],&b[i]);

        for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            bb[++tot].x=i,bb[tot].y=j,bb[tot].v=turn(i,j);

        sort(bb+1,bb+tot+1,cmp);

        for(int i=1;i<=tot;i++)
            if(get(bb[i].x)!=get(bb[i].y))
            {
                fa[get(bb[i].x)]=get(bb[i].y);
                if(get(1)==get(2))
                {
                    ans=bb[i].v;
                    break;
                }
            }
        printf("Scenario #%dnFrog Distance = %.3lfnn",qaq,ans);
    }
    return 0;
}

当然，并查集这个做法也是有缺点的，我们明明知道起点，但并不一定是从起点开始加边的，前面可能加入了很多无用边。

本题也可用最小生成树来解决，就是从出发点开始，不断地从一端已经在最小生成树里，另一端没有在最小生成树里的所有边中加最小边，同时记录下当前已加入的所有边中的最大边权值，直到目标点出现。如上图，依次加入1-4，1-3，3-2，2-5（1为起始点，5为目标点）。最小生成树的时间复杂度为o(n^2)。

并查集加边，最小生成树加点，实际运用时可以看图的稠密度，如果边太多，就加点，边不多，就加边。