kuangbin专题专题四 Frogger POJ - 2253

 

题目链接：https://vjudge.net/problem/poj-2253

思路：

从一号到二号石头的所有路线中，每条路线中都个子选出该路线中两点通路的最长距离，并在这些选出的最长距离选出最短路的那个距离x，

就是青蛙距离，即青蛙至少能跳x米，才能安全的到达二号，因为什么，再看看第一句话。

再想，我们知道，djikstra中的价值数组存的是从u点到其他所有点的最短距离，way[ 1 ] 是u到1的最短距离， way[ x ] 是u到x的最短距离，

我们知道djikstra的时间复杂度是o（n^2），这个时间复杂是是因为我们访问了所有的从一个城市出发到其他城市所有情况（除去已经最优的城市），

有n个城市，去其他（除去最优）的个城市，所有比较次数可以用接近（n^2）表示。

我为什么要说这个呢，我只想表达。。。我只是想强调dijstra保存了最优路线和不确定路线的价值，访问了其他不确定的路线去更新不确定价值的路线，

慢慢得到所有最优路线。

那么，我们可不可以把这个价值数组利用在这个题目上，改变维护方式呢？

我们可以这么想题目意思，价值数组只存一条路线，那么它一定存的是到该城市的最长距离，然后，我们需要把这个最长距离尽可能变小，即最小化最大距离。

那么我们就可以用dijkstra算法来求这个问题，那我们需要怎么维护。

（1）：首先，价值数组初始化一样。

（2）：我们需要找出最小的价值数组，为什么？（里面存的是起始点到该点的所有路线中最小化的最大距离）

（3）：我们找出了最小的价值数组，即得到了城市编号，那么，我们用该点去访问其他不确定的城市。

（4）： 维护方法 :way[ k ] > max( dis[ x ][ k ], way[ x ] ),  max( dis[ x ][ k ], way[ x ] )表示，从起始点到x点所有路线的的最小化的最大距离和x到k的距离选出最大的和

从起始点到k点部分路线的的最小化的最大距离比较，如果k点的从起始点到k点部分路线的的最小化的最大距离比从起始点到x点所有路线的的最小化的最大距离和x到k的距离选出最大的

的大，说明k可以被优化，那么  :way[ k ] =max( dis[ x ][ k ], way[ x ] ),  max( dis[ x ][ k ], way[ x ] )。

（5）：直到最后得到从起始点到其他所有点的最小化最大距离。

( 代码就不加上注释了，只要上面的理解了，代码很容易理解 )

这个题目在思维上还是有点难的，可以慢慢理解。

---

  1 #include <iostream>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cstdio>
  5 #include <string>
  6 #include <cmath>
  7 #include <iomanip>
  8 using namespace std;
  9 
 10 typedef long long ll;
 11 #define inf (1ll << 30) - 1
 12 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
 13 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
 14 #define per(i,j,k) for(int i = (j); i >= (k); i--)
 15 #define per__(i,j,k) for(int i = (j); i > (k); i--)
 16 
 17 const int n = 210;
 18 double p_x[n];
 19 double p_y[n];
 20 double dis[n][n];
 21 bool vis[n];
 22 double way[n];
 23 int n,x,y;
 24 
 25 void init(){
 26     rep(i,1,n) rep(j,1,n){
 27         if(i == j) dis[i][j] = 0;
 28         else dis[i][j] = inf;
 29     }
 30     rep(i,1,n) vis[i] = false;
 31 }
 32 
 33 void input(){
 34 
 35     rep(i,1,n){
 36         cin >> p_x[i] >> p_y[i];
 37     }
 38 }
 39 
 40 inline double fun_dis(double x1, double y1, double x2, double y2){
 41     return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
 42 }
 43 
 44 void calculate_dis(){
 45 
 46     rep(i,1,n){
 47         rep(j,1,n){
 48             double tmp_dis = fun_dis(p_x[i],p_y[i],p_x[j],p_y[j]);
 49             if( tmp_dis < dis[i][j] )
 50                 dis[i][j] = dis[j][i] = tmp_dis;
 51         }
 52     }
 53 }
 54 
 55 void dijkstra(){
 56 
 57     rep(i,1,n) way[i] = dis[1][i];
 58     vis[1] = true;
 59 
 60     rep(i,2,n){
 61 
 62         int x = -1;
 63         double v = inf;
 64 
 65         rep(j,1,n){
 66             if(!vis[j] && v > way[j]) v = way[x = j];
 67         }
 68 
 69         if(x == -1) continue;
 70         vis[x] = true;
 71 
 72         rep(k,1,n){
 73             if(!vis[k] && way[k] > max(way[x], dis[x][k])){
 74                 way[k] = max(way[x], dis[x][k]);
 75             }
 76         }
 77     }
 78 }
 79 
 80 int main(){
 81 
 82 
 83     ios::sync_with_stdio(false);
 84     cin.tie(0);
 85 
 86     int cnt = 0;
 87     while(cin >> n){
 88         if(n == 0) break;
 89 
 90         init();
 91         input();
 92         calculate_dis();
 93         dijkstra();
 94 
 95         cout << "scenario #" << ++cnt << endl;
 96         cout << "frog distance = " << fixed << setprecision(3) << way[2] << endl;
 97         cout << endl;
 98     }   
 99 
100     getchar();getchar();
101 
102     return 0;
103 }