文档章节

poj 2253 Frogger 最小瓶颈路(变形的最小生成树 prim算法解决(需要很好的理解prim))

o
 osc_1ee7cxmx
发布于 2018/08/06 21:12
字数 764
阅读 0
收藏 0

传送门:

http://poj.org/problem?id=2253

Frogger
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 58328   Accepted: 18293

Description

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.

Input

The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy's stone, stone #2 is Fiona's stone, the other n-2 stones are unoccupied. There's a blank line following each test case. Input is terminated by a value of zero (0) for n.

Output

For each test case, print a line saying "Scenario #x" and a line saying "Frog Distance = y" where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.

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

分析:
题目意思:青蛙a在石头1上,青蛙b在石头2上,青蛙a要去找青蛙b玩,问你从从石头1到石头2的最短路里最大的距离是多少

做法:
可以用prim写,但是prim是求MST的,这样只要求1到2的最短路上的最大边就可以了
找j的时候,找到了2就跳出去
注意:
代码里面是0号石头 ,1号石头,而不是分析中的1号,2号石头

code
#include <iostream>
#include <cstdio>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<memory>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
#define max_v 205
struct node
{
    double x,y;
}p[max_v];
double g[max_v][max_v];
int n,c=1;
void init()
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        g[i][j]=INF;
}
void prim(int s)
{
    double lowcost[n];
    int used[n];
    for(int i=0;i<n;i++)
    {
        lowcost[i]=g[s][i];
        used[i]=0;
    }
    double ans=0;
    used[s]=1;
    for(int i=1;i<n;i++)
    {
        int j=0;
        for(int k=0;k<n;k++)
        {
            if(!used[k]&&lowcost[k]<lowcost[j])
                j=k;
        }
        if(j==0)
            break;
        ans=max(ans,lowcost[j]);
        used[j]=1;
        if(j==1)
            break;
        for(int k=0;k<n;k++)
        {
            if(!used[k]&&g[j][k]<lowcost[k])
            {
                lowcost[k]=g[j][k];
            }
        }
    }
    printf("Scenario #%d\n",c++);
    printf("Frog Distance = %0.3f\n\n",ans);
}
double f(int i,int j)
{
    double x=p[i].x-p[j].x;
    double y=p[i].y-p[j].y;
    return sqrt(x*x+y*y);
}
int main()
{
    while(~ scanf("%d",&n))
    {
        if(n==0)
            break;
        for(int i=0;i<n;i++)
        {
            scanf("%lf %lf",&p[i].x,&p[i].y);
        }
        init();
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                g[i][j]=g[j][i]=f(i,j);
            }
        }
        prim(0);
    }
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

树莓派4b + Ubuntu20.04 Server 安装Java8

安装环境: 树莓派4b + Ubuntu20.04 Server 32位 1. 下载jdk https://www.oracle.com/java/technologies/javase/javase-jdk8-downloads.html 2. 解压 tar -zxvf jdk-8u251-linux-arm32-vf......

SummerGao
9分钟前
9
0
项目实战:Qt+OpenCV图像处理与识别算法平台

若该文为原创文章,未经允许不得转载 原博主博客地址:https://blog.csdn.net/qq21497936 原博主博客导航:https://blog.csdn.net/qq21497936/article/details/102478062 本文章博客地址:h...

红模仿_红胖子
12分钟前
7
0
北京智源大会 | AI + 医疗的下一个十年:从公共卫生预警到人类基因密码破解 道翰天琼认知智能api机器人接口。

医疗事关人身安全,要求极高,容错率极低,因此,知识壁垒和技术壁垒都很高。过去,AI系统更多的是服务于终端,辅助医生诊断、决策。但是,医疗很复杂,直接切入终端问题很多。未来十年,AI+...

jackli2020
16分钟前
11
0
源于HystrixCommandStartStream和RollingCommandMaxConcurrencyStream 的 RxJava demo

其实,最近在工作之余看Hystrix源代码已经有一个多月了, 除了对 HystrixCommandProperties ,HystrixCommand 和AbstractCommand 几个类比较了解以外,其余看山不是山,比较懵, 主要是因为H...

专业写BUG的程序员
19分钟前
16
0
聊聊Java中的异常及处理

前言 在编程中异常报错是不可避免的。特别是在学习某个语言初期,看到异常报错就抓耳挠腮,常常开玩笑说编程1分钟,改bug1小时。今天就让我们来看看什么是异常和怎么合理的处理异常吧! 异常...

良许Linux
22分钟前
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部