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,在所有路径中是最小的。

Frog

解决方法:先将边权按从小打到大排序,排序后依次加边,放入集合,每加一条边,判断起始点和结束点是否已在一个集合中。若在,则说明起始点与结束点已连通,当前的边权值为答案。如上图,先加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 #%d\nFrog Distance = %.3lf\n\n",qaq,ans);
    }
    return 0;
}

 

上一篇:[20-05-04][Thinking in Java 6]Java Inheritance 4 - Upcasting


下一篇:算法题 最短路径-02-Frogger