POJ-2253 解题报告

题意简述

湖中有N(2<=N<=200)块石头,标号从1到N。青蛙1在石头1上,青蛙2在石头2上。给定所有的石头坐标。青蛙1试图从石头1到石头2来找青蛙2,它可以经由任意石头组成的路径。在所有可能路径中找出一条路径,使其中最长的一步的长度小于其他路径中最长的一步的长度。

本题可以化简为,点1与点2间存在若干条路径,每条路径中都存在最长的一条边。找出一条路径使得该路径最长边的长度小于其他任意路径最长边。

 算法分析

本题的解法之一是Dijkstra的变形。

初看似乎很难把这道题与单源最短路联系在一起。但我们可以做以下分析:

Dijkstra的贪心思想是基于这样一种前提:

设A→P1→P2→P3→B是A到B的最短路,则其中任意一部分亦是最短路。例如P1→P2→P3必然是P1到P3的最短路。证明很简单。假设P1到P3存在一条更短的路,则A到B便可通过该路获得一条更短的路,与题设“A→P1→P2→P3→B是A到B的最短路”矛盾。

由此便得到了Dijkstra的松弛方程:

枚举u。if (d[v]>d[u]+w(u,v)) then d[v]←d[u]+w(u,v)

其中d为源到点最短路长度。u为中转节点。w为u到v的最短路长度。

这是否能和本题的求解过程等同呢?

对于本题,易得两点间最长边最短的路径可能不唯一。但题目只关心点1到点2所有路径中最短的最长边的长度,并不关心具体路径。所以我们在求解过程中,可以人为定义所求路径满足以下条件:

设A→P1→P2→P3→B是我们想要求得的路径,则它满足其中任意一部分亦满足最长边最短。例如P1→P2→P3亦是所有P1到P3路径中最长边最短的。

这样一来,本题的求解,也满足了与Dijkstra相似的贪心过程。它的松弛方程为:

枚举j。if(dis[j]>max(dis[k],map[k][j])) then dis[j]=max(dis[k],map[k][j])

它的意思是,枚举所有中间点k,源到j的目标路径的最长边,要么在源到k这段,要么在k到j这段。

这样,我们便把Dijkstra算法移植到了本题的求解中。除了松弛方程不同,其他部分均与Dijkstra类似。这里不再赘述。

 

网上的解题报告说这题还可以用最小生成树,日后补充。

 

Problem Status: AC。时间16ms,内存680k

程序样例

 
[c]
#include<stdio.h>
#include<math.h>

double max(double a,double b)
{
return a>b?a:b;
}

double frog(int n,int a[][2])
{
double dis[200],map[200][200],t1,t2,vis[200]={0},min;
int i,j,k;
for(i=0;i<n;i++)
{
dis[i]=999999;
for(j=0;j<n;j++) map[i][j]=999999;
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
t1=(a[i][0]-a[j][0])*(a[i][0]-a[j][0])*1.0;
t2=(a[i][1]-a[j][1])*(a[i][1]-a[j][1])*1.0;
map[i][j]=map[j][i]=sqrt(t1+t2);
}
for(i=1;i<n;i++) dis[i]=map[0][i];
vis[0]=1; dis[0]=0;
for(i=1;i<n;i++)
{
min=999999;
for(j=0;j<n;j++)
if((min>dis[j])&&(vis[j]==0))
{
min=dis[j];
k=j;
}
vis[k]=1;
for(j=0;j<n;j++)
if ((map[k][j]!=999999)&&(!vis[j])&&(dis[j]>max(dis[k],map[k][j])))
dis[j]=max(dis[k],map[k][j]);
}
return dis[1];
}

int main()
{
int x=1,n,i,a[200][2];
double ans;
scanf("%d",&n);
while(n!=0)
{
for(i=0;i<n;i++)
scanf("%d%d",&a[i][0],&a[i][1]);
ans=frog(n,a);
printf("Scenario #%dn",x);
printf("Frog Distance = %.3fnn",ans);
x++;
scanf("%d",&n);
}
return 0;
}
[/c]

Leave a Reply

Your email address will not be published. Required fields are marked *