$$\color{Purple}{kuangbin题解目录}$$
描述
在二维平面上有 $n$ 个石头。
第一个石头上有一个青蛙,第二个石头上也有一个青蛙。
第一个石头上的青蛙要到第二个石头上找另一个青蛙玩耍。
它可以直接跳到第二个石头上,也可以经过一系列中间石头,然后再跳到第二个石头上。
这只青蛙希望,它的跳跃过程中,单次跳跃的最长距离尽可能短。
请你计算并输出这个最长距离的最小可能值。
输入格式
输入包含多组测试数据。
每组数据第一行包含一个整数 $n$。
接下来 $n$ 行,第 $i$ 行包含两个整数 $x_i,y_i$,表示第 $i$ 个石头的位置坐标。
每组数据输入完毕后,还会输入一个空行。
当输入 $n=0$ 时,表示输入结束。
输出格式
每组数据先输出一行 Scenario #x
,其中 $x$ 是组别编号(从 $1$ 开始)。
然后输出一行 Frog Distance = y
,其中 $y$ 是单次跳跃的最长距离的最小可能值,保留三位小数。
每组数据输出完毕后,还要输出一行空行(最后一组数据也不例外)。
数据范围
$2 \\le n \\le 200$,
$0 \\le x_i,y_i \\le 1000$。
输入样例:
2
0 0
3 4
3
17 4
19 4
18 5
0
输出样例:
Scenario #1
Frog Distance = 5.000
Scenario #2
Frog Distance = 1.414
思路
- 题目中的
最长距离的最小可能值
的可理解为:从起点$a$到终点$b$(中间可途径其他点)的过程中跳最远的那次距离,此处可考虑采用最短路
的思想进行变形操作,此处主要采用Dijkstra算法
,其他的单源最短路算法
亦可解决;- 假设起点是$a$,终点是$b$,假设中间途径$c$点,其中
dist[i]
表示从起点$a$出发到达任意一点$i$的中间任意两块石头的最大距离的最小值
,此时$\color{Green}{dist[b]=min(dist[b],max(dist[c],val[c][b]))}$,而原始的最短路执行的操作是$\color{Red}{dist[b]=min(dist[b],dist[c]+val[c][b])}$;- 此处可考虑通过
最小生成树
中的Kruskal算法
解决,依次把边从小到大加进来,直至起点遇到第$2$号石头(此时起点一定与第$2$号石头连通,连上的边恰好是当前放入的最大值),输出该边即可;- 一个细节: $double$型的数组初始化为无穷($\infty$)时,不能用
memset
初始化,可通过循环方式
进行初始化.- 最短路之
最小化最大值
模型(例题:青蛙),最短路之最大化最小值
模型(例题:货物运输)
代码
- $Dijkstra$(朴素版)
// Problem: 青蛙
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4243/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
// Date: 2023-01-22 15:04:43
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 210
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n;
struct Point{
int x;
int y;
}point[MAXN];
double val[MAXN][MAXN];
int vis[MAXN];
double dist[MAXN];
double get_dist(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void Dijkstra(int start)
{
memset(vis,0,sizeof(vis));
//memset(dist,0x3f,sizeof(dist));
//注:double类型采用memset赋值为无穷大不可取,实际数字是0.000476792(非常小的整数)
//故可通过循环方式置为无穷
for(int i=1;i<=n;i++)
dist[i]=inf;
/*
for(int i=1;i<=n;i++)
cout << dist[i] << endl;*/
dist[start]=0;
for(int i=1;i<=n-1;i++)//重复进行n-1次
{
int pos=-1;//找到未标记结点中dist最小的
for(int j=1;j<=n;j++)
if(vis[j]==0&&(pos==-1||dist[j]<dist[pos]))
pos=j;
vis[pos]=1;
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],max(val[pos][j],dist[pos]));
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int Cas=1;
while(cin >> n)
{
if(n==0)
break;
for(int i=1;i<=n;i++)
cin >> point[i].x >> point[i].y;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
val[i][j]=val[j][i]=get_dist(point[i],point[j]);
/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout << val[i][j]<< ' ';
cout << endl;
}*/
Dijkstra(1);
printf("Scenario #%d\n",Cas++);
printf("Frog Distance = %.3f\n\n",dist[2]);
}
return 0;
}
- $Dijkstra$(堆优化版)
注: 该题是一个稠密图
,用堆优化版的时间会相对于朴素版较长
// Problem: 青蛙
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4243/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
// Date: 2023-01-22 15:04:43
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define MAXN 210
#define MAXM 40010
using namespace std;
typedef long long ll;
typedef pair<double,int> PDI;
const int inf=0x3f3f3f3f;
int n;
struct Point{
int x;
int y;
}point[MAXN];
int vis[MAXN];
double dist[MAXN];
int head[MAXN],ed[MAXM],nex[MAXM],idx;
double val[MAXM];
double get_dist(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void add(int a,int b,double c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
void Dijkstra(int start)
{
memset(vis,0,sizeof(vis));
//memset(dist,0x3f,sizeof(dist));
//注:double类型采用memset赋值为无穷大不可取,实际数字是0.000476792(非常小的整数)
//故可通过循环方式置为无穷
for(int i=1;i<=n;i++)
dist[i]=inf;
dist[start]=0;
priority_queue<PDI,vector<PDI>,greater<PDI> > q;
q.push({0,start});//把起点压入优先队列中
while(q.size()>0)
{
PDI temp=q.top();//取出距离起点最近的点
q.pop();
double temp_dis=temp.first;
int temp_pos=temp.second;
if(vis[temp_pos]==1)//当前点已走过
continue;
vis[temp_pos]=1;
for(int i=head[temp_pos];i!=-1;i=nex[i])
{
int j=ed[i];
if(vis[j]==1)
continue;
if(dist[j]>max(temp_dis,val[i]))
{
dist[j]=max(temp_dis,val[i]);
q.push({dist[j],j});
}
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int Cas=1;
while(cin >> n)
{
if(n==0)
break;
//记得初始化链式前向星
memset(head,-1,sizeof(head));
idx=0;
for(int i=1;i<=n;i++)
cin >> point[i].x >> point[i].y;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
//记得加双向边
add(i,j,get_dist(point[i],point[j]));
add(j,i,get_dist(point[i],point[j]));
}
Dijkstra(1);
printf("Scenario #%d\n",Cas++);
printf("Frog Distance = %.3f\n\n",dist[2]);
}
return 0;
}
- $Kruskal$(最小生成树)
// Problem: 青蛙
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4243/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
// Date: 2023-01-22 15:04:43
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define MAXN 210
#define MAXM 40010
using namespace std;
typedef long long ll;
typedef pair<double,int> PDI;
const int inf=0x3f3f3f3f;
int n;
int fa[MAXN];
struct Point{
int x;
int y;
}point[MAXN];
double get_dist(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
struct Node{
int start_;
int end_;
double dist;
}v[MAXN*MAXN];
int cmp(Node a,Node b)
{
return a.dist<b.dist;
}
int find(int x)
{
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
void join(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
fa[fx]=fy;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int Cas=1;
while(cin >> n)
{
if(n==0)
break;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=n;i++)
cin >> point[i].x >> point[i].y;
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
v[cnt++]={i,j,get_dist(point[i],point[j])};
sort(v,v+cnt,cmp);
for(int i=0;i<cnt;i++)
{
join(v[i].start_,v[i].end_);
if(find(1)==find(2))
{
printf("Scenario #%d\n",Cas++);
printf("Frog Distance = %.3f\n\n",v[i].dist);
break;
}
}
}
return 0;
}