（今天才学会Prim 尴尬……）

这题好久之前（四个月之前）就写过。。 当时WA了……抄得题解

现在终于搞对了。

// by SiriusRen#include 
     
      #include 
      
       #include 
       
        #define N 1005using namespace std;int n,now;double map[N][N],h[N][N],low,high,ans,d[N],minn;bool vis[N];struct Node{
    int x,y,h;}v[1005];void prim(double x){    for(int i=1;i<=n;i++)d[i]=h[1][i]-x*map[1][i];    memset(vis,0,sizeof(vis)),vis[1]=1;    now=1,ans=0;    for(int i=1;i
        
         d[j])minn=d[j],now=j;        ans+=minn,vis[now]=1;        for(int j=1;j<=n;j++)if(!vis[j]&&d[j]>h[now][j]-x*map[now][j])d[j]=h[now][j]-x*map[now][j];    }}int main(){    while(scanf("%d",&n)&&n){        high=N*N*N,low=0;         for(int i=1;i<=n;i++)scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].h);        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++){                map[i][j]=sqrt(1.0*(v[i].x-v[j].x)*(v[i].x-v[j].x)+1.0*(v[i].y-v[j].y)*(v[i].y-v[j].y));                h[i][j]=abs(v[i].h-v[j].h);            }        while(high-low>=1e-6){            double mid=(high+low)/2;            prim(mid);            if(ans>0)low=mid;            else high=mid;        }        printf("%.3lf\n",low);    }}