我就不说题意了，为了使A/B最大，就应该是B越小，故可以先求出n个点的最小生成树。因此，可以枚举每一条边，假设最小生成树的值是B, 而枚举的那条边长度是edge[i][j],  如果这一条边已经是属于最小生成树上的，那么最终式子的值是A/(B-edge[i][j])。如果这一条不属于最小生成树上的， 那么添加上这条边，就会有n条边，那么就会使得有了一个环，为了使得它还是一个生成树，就要删掉环上的一棵树。 为了让生成树尽量少，那么就要删掉除了加入的那条边以外，权值最大的那条路径。 假设删除的那个边的权值是Max[i][j], 那么就是A/(B-Max[i][j]).

这题的关键也在于怎样求出次小生成树;

先用prim求出最小生成树T.在prim的同时，用一个矩阵max[u][v] 记录 在T中连结任意两点u,v的唯一的路中权值最大的那条边的权值.这是很容易做到的，因为prim是每次增加一个结点s, 而设已经标号了的结点集合为W, 则W中所有的结点到s的路中的最大权值的边就是当前加入的这条边.

1 #include
      
        2 #include
       
         3 #include
        
          4 const int N=1010; 5 const double inf=1e14; 6 using namespace std; 7  8 struct Point{ 9     int x,y,z;10 }point[N];11 12 int n;13 double edge[N][N];14 int nearvex[N];//保存前驱15 double  lowcost[N]; 16 double sum;17 18 int used[N][N];19 int visited[N];20 double  Max[N][N];//用来保存最小生成树中两点之间的权值最大的边21 22 23 void prim(int v0){24     sum=0;25     memset(used,0,sizeof(used));26     memset(visited,0,sizeof(visited));27     memset(Max,0,sizeof(Max));28     for(int i=1;i<=n;i++){29         lowcost[i]=edge[v0][i];30         nearvex[i]=v0;31     }32     visited[v0]=1;33     for(int i=1;i
         
          lowcost[v]?Max[k][nearvex[v]]:lowcost[v]);49                 }50                 if(!visited[k]&&edge[v][k]
          
           (point[i].z+point[j].z)*1.0/(sum-edge[i][j])?r:(point[i].z+point[j].z)*1.0/(sum-edge[i][j]));81                 }else if(!used[i][j]){82                     r=(r>(point[i].z+point[j].z)*1.0/(sum-Max[i][j])?r:(point[i].z+point[j].z)*1.0/(sum-Max[i][j]));83                 }84             }85         }86         printf("%.2lf\n",r);87     }88     return 0;89 }