这道题的提议就是就最小生成树中的最大权所以我用了最小生成树prim算法

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #define maxn 207 using namespace std; const double inf = 99999999.0; bool vt[maxn]; double dis[maxn],map[maxn][maxn]; struct node {
    double x,y; }tagp[maxn]; int n; double ans; void init() {
    int i,j; for (i = 0; i < n; ++i)     {
    for (j = 0; j < n; ++j)         {
    if (i == j) map[i][j] = 0; else map[i][j] = inf;         }     } } double length(int i,int j) {
    double x = tagp[i].x - tagp[j].x; double y = tagp[i].y - tagp[j].y; double s = sqrt(x*x + y*y); return s; } void prim() {
    int i,j,k; double min;     ans = 0.0; for (i = 0; i < n; ++i)     {
            vt[i] = false;         dis[i] = map[0][i];     }     vt[0] = true; for (k = 1; k < n; ++k)     {
            j = 0; min = inf; for (i = 1; i < n; ++i)         {
    if (!vt[i] && dis[i] < min)             {
                    j = i; min = dis[i];             }         }         vt[j] = true; if (ans < min)         ans = min; if (j == 1) break; for (i = 1; i < n; ++i)         {
    if (!vt[i] && dis[i] > map[i][j])             dis[i] = map[i][j];         }     } } int main() {
    int i,j,cas = 1; while (~scanf("%d",&n))     {
    if (!n) break;         init(); for (i = 0; i < n; ++i)         {
                cin>>tagp[i].x>>tagp[i].y;         } for (i = 0; i < n; ++i)         {
    for (j = 0; j < n; ++j)             {
                    map[i][j]  = length(i,j);             }         }         prim();         printf("Scenario #%d\n",cas++);         printf("Frog Distance = %.3lf\n\n",ans);     } return 0; }
         
        
       
      

这道题可以是Dijkstra算法的变形，原来Dijkstra求最短时dis[i]里面存的是到起点的最短距离，而现在则是存由起点到i的最短路径里面的最大边权值了。。

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #define maxn 207 using namespace std; double dis[maxn],map[maxn][maxn]; bool vt[maxn]; int n; const double inf = 9999999.0; struct node {
    double x,y; }p[maxn]; double Max(double a,double b) {
    return a > b ? a:b; } double Min(double a,double b) {
    return a < b ? a:b; } void init() {
    int i,j; for (i = 0; i < n; ++i)     {
            vt[i] = false; for (j = 0; j < n; ++j)         {
    if (i == j) map[i][j] = 0; else map[i][j] = inf;         }     } } double length(int i,int j) {
    double x = p[i].x - p[j].x; double y = p[i].y - p[j].y; double s = 1.0*sqrt(x*x + y*y); return s; } void Dijkstra() {
    int i,j,k; double min; for (i = 0; i < n; ++i)     {
            dis[i] = map[0][i];     }     vt[0] = true;; for (k = 1; k < n; ++k)     {
            j = 0; min = inf; for (i = 1; i < n; ++i)         {
    if (!vt[i] && dis[i] < min)             {
                    j = i; min = dis[i];             }         }         vt[j] = true; for (i = 0; i < n; ++i)         {
    if (!vt[i])             {
                    dis[i] = Min(dis[i],Max(map[i][j],dis[j]));//关键的改进是在这里，Min是确保最短路径 //Max是求边权值最大。。             }         }     } } int main() {
    int i,j,cas = 1; while (~scanf("%d",&n))     {
    if (!n) break;         init(); for (i = 0; i < n; ++i)         {
               cin>>p[i].x>>p[i].y;         } for (i = 0; i < n; ++i)         {
    for (j = 0; j < n; ++j)             {
                    map[i][j] = map[j][i] = length(i,j);             }         }         Dijkstra();         printf("Scenario #%d\n",cas++);         printf("Frog Distance = %.3lf\n\n",dis[1]);     } return 0; }