POJ 2253 Frogger(并查集+二分)
http://poj.org/problem?id=2253
题意:给你N个石头的坐标(x,y),现在青蛙要从第一个石头跳到第二个石头上去,但是青蛙每次最大的跳跃距离有限制.所以现在问你青蛙从第一个石头跳到第二个石头的最短跳跃距离是多少?
分析:
网上说这题有最短路径解的,生成树解的.本来我是冲着最短路径解法来的,但是看了一遍我觉得这题用二分+并查集(判断1点与2点是否连通)才是比较直观的方法吧.
首先我们二分出mid值表示青蛙每次能跳跃的距离,然后我们遍历所有的边,只要当前边的长度<=mid,就合并当前边连接的两个点.最后判断1号点与2号点是否在同一个连通分量,即可知道单次mid的跳跃距离是否足够.
AC代码:
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=200+10;
int n;
double x[maxn],y[maxn];
double d[maxn][maxn];
int fa[maxn];
int find(int i)
{
if(fa[i]==-1) return i;
return fa[i] = find(fa[i]);
}
void bind(int i,int j)
{
i=find(i);
j=find(j);
if(i!=j) fa[i]=j;
}
bool ok(double mid)
{
memset(fa,-1,sizeof(fa));
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)if(d[i][j]<mid)
bind(i,j);
}
return find(1)==find(2);
}
int main()
{
int kase=0;
while(scanf("%d",&n)==1&&n)
{
for(int i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
memset(d,0,sizeof(d));
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
d[i][j]=d[j][i]= sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
double L=0,R=d[1][2];
while(R-L>1e-7) //这里是1e-7 不是1e7
{
double mid = (R+L)/2;
if(ok(mid)) R=mid;
else L=mid;
}
printf("Scenario #%d\nFrog Distance = %.3lf\n\n",++kase,R);
}
return 0;
}
分享到:
相关推荐
北大POJ2253-Frogger【Floyd】 解题报告+AC代码
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
pku acm 2253 Frogger 代码 单元最短路径 Dijkstra算法
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
西北工业大学POJ试题C++答案代码+课程设计
这份代码用C++实现了经典算法并查集,来源于poj题目1182
北大POJ2002-Squares 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ1837-Balance 解题报告+AC代码
北大POJ2503-Babelfish 解题报告+AC代码
北大POJ1201-Intervals 解题报告+AC代码
北大POJ1011-Sticks 解题报告+AC代码
北大POJ1039-Pipe 解题报告+AC代码