http://poj.org/problem?id=2253
题意 : 题目是说,有这样一只青蛙Freddy,他在一块石头上,他呢注意到青蛙Fiona在另一块石头上,想去拜访,但是两块石头太远了,所以他只有通过别的石头跳过去,所以,从他的石头到Fiona的石头每一条可走的路,假设是n条,就需要你求出frog distance,这个所谓的距离就是指这n条路中,每条路选取组成这条路中最长的那边,最后一共有n条边,找这n条边里最短的那一条输出。
思路 : 就是一个最短路的问题,不过不需要求最短路的权值和,只需要求出最大跳即可,还要注意,不管几行坐标,前两行分别是Freddy的位置和Fiona的位置,最后输出,不过很多人倒是用了克鲁斯卡尔和prim做的,我一直不明白这个题为什么会转化成最小生成树.........好吧,我才疏学浅..........
这是几组测试数据:
Scenario #
Frog Distance = 5.000 Scenario #
Frog Distance = 1.414 Scenario #
Frog Distance = 1.414 Scenario #
Frog Distance = 1.000 Scenario #
Frog Distance = 134.350 Scenario #
Frog Distance = 1.414 Scenario #
Frog Distance = 1408.557
对了,每一行输出有一空行,因为一开始没注意结果PE了一次,又一次证明了我有多粗心。。。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std; const int maxn = ;
const int oo = << ; double map[maxn][maxn];
int n,m;
double x[maxn],y[maxn]; void floyd()
{
for(int k = ; k < n ; k++)
{
for(int i = ; i < n ; i++) //主要针对由i到j的松弛,最终任意两点间的权值都会被分别松弛为最大跳的最小(但每个两点的最小不一定相同)
{
for(int j = ; j < n ; j++)
{
if(map[i][j] > map[i][k]&&map[i][j] > map[k][j])//当边ik,kj的权值都小于ij时,则走i->k->j路线,否则走i->j路线
{
if(map[i][k] > map[k][j]) //当走i->k->j路线时,选择max{ik,kj},只有选择最大跳才能保证连通
map[i][j] = map[i][k];
else
map[i][j] = map[k][j];
} }
}
}
} void Init()
{
for(int i = ; i < n ; i++)
{
for(int j = ; j < n ; j++)
{
map[i][j] = oo ;
}
map[i][i] = ;
}
} int main()
{
int cnt = ;
while(~scanf("%d",&n)&&n)
{
cnt++;
Init();
for(int i = ; i < n ; i++)
{
scanf("%lf %lf",&x[i],&y[i]);
}
for(int i = ; i < n ; i++)
{
for(int j = ; j < n ; j++)
{
map[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
}
floyd();
printf("Scenario #%d\n",cnt);
printf("Frog Distance = %.3f\n\n",map[][]);
}
return ;
}
POJ 2253 Frogger(floyd)的更多相关文章
-
POJ 2253 Frogger (Floyd)
Frogger Time Limit: 1000MS Memory Limit: 65536K Total Submissions:57696 Accepted: 18104 Descript ...
-
POJ 2253 Frogger(最小生成树)
青蛙跳跃,题意大概是:青蛙从起点到终点进行一次或多次的跳跃,多次跳跃中肯定有最大的跳跃距离.求在所有的跳跃中,最小的最大跳跃距离SF-_-(不理解?看题目吧). 可以用最小生成树完成.以起点为根,生成 ...
-
poj 2253 Frogger(floyd变形)
题目链接:http://poj.org/problem?id=1797 题意:给出两只青蛙的坐标A.B,和其他的n-2个坐标,任一两个坐标点间都是双向连通的.显然从A到B存在至少一条的通路,每一条通路 ...
-
POJ. 2253 Frogger (Dijkstra )
POJ. 2253 Frogger (Dijkstra ) 题意分析 首先给出n个点的坐标,其中第一个点的坐标为青蛙1的坐标,第二个点的坐标为青蛙2的坐标.给出的n个点,两两双向互通,求出由1到2可行 ...
-
POJ 2253 Frogger(dijkstra 最短路
POJ 2253 Frogger Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fion ...
-
poj 2253 Frogger (dijkstra最短路)
题目链接:http://poj.org/problem?id=2253 Frogger Time Limit: 1000MS Memory Limit: 65536K Total Submissi ...
-
POJ 2253 Frogger(最短路&;Floyd)题解
题意:想给你公青蛙位置,再给你母青蛙位置,然后给你剩余位置,问你怎么走,公青蛙全力跳的的最远距离最小. 思路:这里不是求最短路径,而是要你找一条路,青蛙走这条路时,对他跳远要求最低.这个思想还是挺好迁 ...
-
[ACM] POJ 2253 Frogger (最短路径变形,每条通路中的最长边的最小值)
Frogger Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 24879 Accepted: 8076 Descript ...
-
POJ 2253 Frogger(Dijkstra变形——最短路径最大权值)
题目链接: http://poj.org/problem?id=2253 Description Freddy Frog is sitting on a stone in the middle of ...
随机推荐
-
关于c++
http://www.ezlippi.com/blog/2014/12/c-open-project.html
-
创建webservice实例
http://blog.csdn.net/haiyanstudent/article/details/32148207
-
AndroidPn
客户端的主要包说明 org.androidpn.client包下的文件 public class Constants { //包含静态数据 public class InvalidFormatExc ...
-
Java和C++中的static
1.Java类中的static变量和static方法会在类装载的过程中就得到内存分配,然后就会进行初始化工作.最多可能会被初始化3次,静态代码块的执行在main方法之前. static变量不可以在构造 ...
-
几个较好的SQL速查手册网址
微软 SQL server 数据库开发手册 数据库设计 Transact-SQL 速查手册 数据库设计 MySQL 中文参考手册速查 结构化查询语言 SQL 学习手册速查 转自:http://www. ...
-
SQL 面试题(一)
问题来自于CSDN问答,练练SQL吧. 测试数据SQL代码: if OBJECT_ID('td_ls_2') is not null drop table td_ls_2 go if OBJECT_I ...
-
delphi TToolBar
工具栏 的属性 xe4的事件 Customizable OnCustomizeCanDelete OnCustomizeCanInsert OnCustomized OnCustomizeAdded ...
-
C语言的一些误用和知识总结
现在学嵌入式的话,最主要是要把C语言熟悉,比如指针,链表,共用体,结构体等,还是得听老师的话.. 在学习单片机的时候才真正知道C语言是什么它是来干什么的~但是C语言用到嵌入式只是它小小的一部分他的应用 ...
-
windows 上用 docker 部署aspnetcore 2.0
首先下载docker for windows 并且 安装. 这其中需要显卡支持虚拟化 windows系统升级到专业版 bois 启用虚拟 通过vs2017 创建一个net core ap ...
-
【提取元素的值 】【追加文本append】【删除文本remove】【class的操作】【读取元素的宽度,高度】
1.取值 $("#test").text() //取id=test里面的文字 $("#test&qu ...