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

/*
   题意：就是源点到终点有多条的路径，每一条路径中都有一段最大的距离！
    求这些路径中最大距离的最小值！
    
   Dijkstra, Floyd, spfa都是可以的！只不过是将松弛的条件变一下就行了！

   想了一下，这道题用最小生成树做也可以啊，图总是连通的嘛!所以建一棵最小
   生成树，然后dfs一下，从源点1，到终点2的路径上，查找边长最大的路径！ 
   附上代码..... 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#define INF 0x3f3f3f3f*1.0
using namespace std;
struct node{
    double x, y;       
};
node nd[205];
double g[205][205];
double d[205];
int vis[205];
int n;

void Dijkstra(){ 
   memset(vis, 0, sizeof(vis));
   d[1]=0.0;
   int root=1;
   vis[1]=1;
   for(int i=2; i<=n; ++i)
      d[i]=INF;
   for(int j=1; j<n; ++j){
       int p;
       double minL=INF;
       for(int i=1; i<=n; ++i){
          double dist;
          if(!vis[i] && d[i]> (dist=max(d[root], g[root][i])))
              d[i]=dist;
          if(!vis[i] && minL>d[i]){
              minL=d[i];
              p=i;           
          }
       }
       if(minL==INF) return;
       root=p;
       vis[root]=1;
   }
}

int main(){
   int cnt=0;
   while(cin>>n && n){
       for(int i=1; i<=n; ++i)
          for(int j=1; j<=n; ++j)
             g[i][j]=INF;
       for(int i=1; i<=n; ++i){
          double u, v;
          cin>>nd[i].x>>nd[i].y;
          for(int j=1; j<i; ++j){
             u=nd[i].x-nd[j].x;        
             v=nd[i].y-nd[j].y;
             g[i][j]=g[j][i]=sqrt(u*u + v*v);
          }        
       }
       Dijkstra();
       cout<<"Scenario #"<<++cnt<<endl<<"Frog Distance = ";
       cout<<fixed<<setprecision(3)<<d[2]<<endl;
       cout<<endl;
   }
   return 0;    
}

//最小生成树思想
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#define INF 0x3f3f3f3f*1.0
using namespace std;
struct node{
    double x, y;     
};
node nd[205];

struct EDGE{
   int u, v;
   double dist;       
};
EDGE edge[21000];

bool cmp(EDGE a, EDGE b){
   return a.dist < b.dist;     
}

double g[205][205];

int vis[205], f[205];
int n;

int getFather(int x){
   return x==f[x] ? x : f[x]=getFather(f[x]);    
}

bool Union(int a, int b){
     int fa=getFather(a), fb=getFather(b);
     if(fa!=fb){
         f[fa]=fb;
         return true;           
     } 
     return false;
}
double dd;
bool dfs(int cur, double ddd){
    vis[cur]=1;
    if(cur==2){
       dd=ddd;
       return true;           
    }
    for(int i=1; i<=n; ++i)
       if(g[cur][i]!=INF && !vis[i]){
            if(ddd<g[cur][i]){
               if(dfs(i, g[cur][i]))  return true;
            }
            else if(dfs(i, ddd)) return true;           
       } 
    return false;    
}

int main(){
   int cnt=0;
   while(cin>>n && n){
       for(int i=1; i<=n; ++i)
          for(int j=1; j<=n; ++j)
             g[i][j]=INF;
       int count=0;
       for(int i=1; i<=n; ++i){
          double u, v;
          cin>>nd[i].x>>nd[i].y;
          for(int j=1; j<i; ++j){
             u=nd[i].x-nd[j].x;        
             v=nd[i].y-nd[j].y;
             edge[count].u=i;
             edge[count].v=j;
             edge[count++].dist=sqrt(u*u + v*v);
          }        
       }
       sort(edge, edge+count, cmp);
       for(int i=1; i<=n; ++i)
          f[i]=i;
       for(int i=0; i<count; ++i){
           int u, v;
           if(Union(u=edge[i].u, v=edge[i].v))
              g[u][v]=g[v][u]=edge[i].dist;        
       }
       memset(vis, 0, sizeof(vis));
       dfs(1, 0.0);
       cout<<"Scenario #"<<++cnt<<endl<<"Frog Distance = ";
       cout<<fixed<<setprecision(3)<<dd<<endl;
       cout<<endl;
   }
   return 0;    
}