POJ 2253 Frogger（floyd）

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）

最新文章

热门文章