poj2253 Frogger（最短路变型或者最小生成树）

  1 /*
  2    题意：就是源点到终点有多条的路径，每一条路径中都有一段最大的距离！
  3     求这些路径中最大距离的最小值！
  4     
  5    Dijkstra, Floyd, spfa都是可以的！只不过是将松弛的条件变一下就行了！
  6 
  7    想了一下，这道题用最小生成树做也可以啊，图总是连通的嘛!所以建一棵最小
  8    生成树，然后dfs一下，从源点1，到终点2的路径上，查找边长最大的路径！ 
  9    附上代码..... 
 10 */
 11 #include<iostream>
 12 #include<cstdio>
 13 #include<algorithm>
 14 #include<cstring>
 15 #include<cmath>
 16 #include<iomanip>
 17 #define INF 0x3f3f3f3f*1.0
 18 using namespace std;
 19 struct node{
 20     double x, y;       
 21 };
 22 node nd[205];
 23 double g[205][205];
 24 double d[205];
 25 int vis[205];
 26 int n;
 27 
 28 void Dijkstra(){ 
 29    memset(vis, 0, sizeof(vis));
 30    d[1]=0.0;
 31    int root=1;
 32    vis[1]=1;
 33    for(int i=2; i<=n; ++i)
 34       d[i]=INF;
 35    for(int j=1; j<n; ++j){
 36        int p;
 37        double minL=INF;
 38        for(int i=1; i<=n; ++i){
 39           double dist;
 40           if(!vis[i] && d[i]> (dist=max(d[root], g[root][i])))
 41               d[i]=dist;
 42           if(!vis[i] && minL>d[i]){
 43               minL=d[i];
 44               p=i;           
 45           }
 46        }
 47        if(minL==INF) return;
 48        root=p;
 49        vis[root]=1;
 50    }
 51 }
 52 
 53 int main(){
 54    int cnt=0;
 55    while(cin>>n && n){
 56        for(int i=1; i<=n; ++i)
 57           for(int j=1; j<=n; ++j)
 58              g[i][j]=INF;
 59        for(int i=1; i<=n; ++i){
 60           double u, v;
 61           cin>>nd[i].x>>nd[i].y;
 62           for(int j=1; j<i; ++j){
 63              u=nd[i].x-nd[j].x;        
 64              v=nd[i].y-nd[j].y;
 65              g[i][j]=g[j][i]=sqrt(u*u + v*v);
 66           }        
 67        }
 68        Dijkstra();
 69        cout<<"Scenario #"<<++cnt<<endl<<"Frog Distance = ";
 70        cout<<fixed<<setprecision(3)<<d[2]<<endl;
 71        cout<<endl;
 72    }
 73    return 0;    
 74 }
 75 
 76 //最小生成树思想
 77 #include<iostream>
 78 #include<cstdio>
 79 #include<algorithm>
 80 #include<cstring>
 81 #include<cmath>
 82 #include<iomanip>
 83 #define INF 0x3f3f3f3f*1.0
 84 using namespace std;
 85 struct node{
 86     double x, y;     
 87 };
 88 node nd[205];
 89 
 90 struct EDGE{
 91    int u, v;
 92    double dist;       
 93 };
 94 EDGE edge[21000];
 95 
 96 bool cmp(EDGE a, EDGE b){
 97    return a.dist < b.dist;     
 98 }
 99 
100 double g[205][205];
101 
102 int vis[205], f[205];
103 int n;
104 
105 int getFather(int x){
106    return x==f[x] ? x : f[x]=getFather(f[x]);    
107 }
108 
109 bool Union(int a, int b){
110      int fa=getFather(a), fb=getFather(b);
111      if(fa!=fb){
112          f[fa]=fb;
113          return true;           
114      } 
115      return false;
116 }
117 double dd;
118 bool dfs(int cur, double ddd){
119     vis[cur]=1;
120     if(cur==2){
121        dd=ddd;
122        return true;           
123     }
124     for(int i=1; i<=n; ++i)
125        if(g[cur][i]!=INF && !vis[i]){
126             if(ddd<g[cur][i]){
127                if(dfs(i, g[cur][i]))  return true;
128             }
129             else if(dfs(i, ddd)) return true;           
130        } 
131     return false;    
132 }
133 
134 int main(){
135    int cnt=0;
136    while(cin>>n && n){
137        for(int i=1; i<=n; ++i)
138           for(int j=1; j<=n; ++j)
139              g[i][j]=INF;
140        int count=0;
141        for(int i=1; i<=n; ++i){
142           double u, v;
143           cin>>nd[i].x>>nd[i].y;
144           for(int j=1; j<i; ++j){
145              u=nd[i].x-nd[j].x;        
146              v=nd[i].y-nd[j].y;
147              edge[count].u=i;
148              edge[count].v=j;
149              edge[count++].dist=sqrt(u*u + v*v);
150           }        
151        }
152        sort(edge, edge+count, cmp);
153        for(int i=1; i<=n; ++i)
154           f[i]=i;
155        for(int i=0; i<count; ++i){
156            int u, v;
157            if(Union(u=edge[i].u, v=edge[i].v))
158               g[u][v]=g[v][u]=edge[i].dist;        
159        }
160        memset(vis, 0, sizeof(vis));
161        dfs(1, 0.0);
162        cout<<"Scenario #"<<++cnt<<endl<<"Frog Distance = ";
163        cout<<fixed<<setprecision(3)<<dd<<endl;
164        cout<<endl;
165    }
166    return 0;    
167 }