其实这个题目读懂题目意思就已经成功一半了。下面是从别处找来的翻译。

Description

一只叫Freddy的青蛙蹲坐在湖中的一块石头上。突然他发现一只叫Fiona的青蛙在湖中的另一块石头上。Freddy想要跟Fiona约会,但由于湖水太脏,他不想游泳过去而是跳过去找Fiona。
很不幸,Fiona所在的石头距离他有点远,甚至超出了他的跳跃能力。然而Freddy注意到湖中还有一些其他的石头。这些石头也许会将这个很长的跳跃距离化成若干个短的跳跃距离。
我们定义“青蛙距离”为Freddy跳到Fiona那里所需要的若干次跳跃中最长的那一次。现在给你Freddy,Fiona,以及湖中其他石头的坐标,让你求出最短的“青蛙距离”。

这个所谓的“最短青蛙距离”到底是什么鬼呢,网上说法各有各的理,看了好几个人的解释,其实就是一个求最小生成树里面的最大权的问题,既然这样就好解了,我们以前用prim算法求最小生成树的权值之和时用了一个sum的变量来存储这些权,现在我只要把这个sum改成imax,用imax来存他的最大权就好了,当然,要考虑Freddy什么时候跳到了Fiona的石头上(这里没判断,WA了好几次),还有就是输出格式的问题,输出最大权后是要换2行的!

题目:飞机票直达(B - Frogger


下面是prim算法的代码(喜欢prim是因为他的代码简单而且效率好像高一点)


#include <iostream>
#include <cstdio>
#include <cmath>
#include <memory.h>
using namespace std;
const int maxn=1000+1;
const int inf=9999999;
double omap[maxn][maxn];
bool flag[maxn];
int x[maxn], y[maxn];
int i, j, icase=1, n;
void Init()
{
    memset(flag, 0, sizeof(flag));
    memset(x, 0, sizeof(x));
    memset(y, 0, sizeof(y));
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)omap[i][j]=inf;      //初始化最大值
    for(i=1;i<=n;i++)scanf("%d%d", &x[i], &y[i]);  //获得坐标值
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)
        omap[i][j]=sqrt((double)(x[j]-x[i])*(x[j]-x[i]) + (y[j]-y[i])*(y[j]-y[i])); //获得距离值
}
double Prim()
{
    double imax=0, minlen;
    int t;
    for(i=1;i<n;i++)
    {
        minlen=999999;
        for(j=2;j<=n;j++)
        {
            if(!flag[j]&&omap[1][j]<minlen)
            {
                minlen=omap[1][j];
                t=j;
            }
        }
        flag[t]=1;
        if(minlen>imax)imax=minlen;     //判断是否到达
        if(t==2)return imax;
        for(j=2;j<=n;j++)
        {
            if(!flag[j] && omap[t][j]<omap[1][j])
            {
                omap[1][j]=omap[t][j];
            }
        }
    }
}
int main()
{
    while(scanf("%d", &n)!=EOF && n)
    {
        Init();
        double ans=Prim();
        printf("Scenario #%d\n", icase++);
        printf("Frog Distance = %.3lf\n\n", ans);       //两个\n。不然PE
    }
    return 0;
}