#include #include #include const int N=1010; const double inf=1e14; using namespace std; struct Point{ int x,y,z; }point[N]; int n; double edge[N][N]; int nearvex[N]; double lowcost[N]; double sum; int used[N][N]; int visited[N]; double Max[N][N]; void prim(int v0){ sum=0; memset(used,0,sizeof(used)); memset(visited,0,sizeof(visited)); memset(Max,0,sizeof(Max)); for(int i=1;i<=n;i++){ lowcost[i]=edge[v0][i]; nearvex[i]=v0; } visited[v0]=1; for(int i=1;ilowcost[v]?Max[k][nearvex[v]]:lowcost[v]); } 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])); }else if(!used[i][j]){ 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])); } } } printf("%.2lf\n",r); } return 0; }