题目链接：http://poj.org/problem?id=2728
题目大意：
在这么一个图中求一棵生成树,这棵树的单位长度的花费最小是多少？

思路：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<math.h>

#define LL long long
using namespace std;

LL x[1005], y[1005], z[1005];
LL mp[1005][1005];
double w[1005][1005];

int check(double mid, int n){

    double dis[1005]={0};
    bool vis[1005]={0};
    double sum=0;
    for(int i=1; i<=n; i++){
        dis[i]=mp[1][i]-mid*w[1][i];//以dis[i]为参照，选取最小的n-1个
    }
    vis[1]=1;
    int N=n-1;
    while(N--){
        double min_f=(1ll<<50);
        int v=-1;
        for(int j=1; j<=n; j++){
            if(vis[j]==0&&dis[j]<min_f){
                min_f=dis[j];
                v=j;
            }
        }
        sum+=min_f;
        vis[v]=1;
        for(int i=1; i<=n; i++){
            if(vis[i]==0&&mp[v][i]-mid*w[v][i]<dis[i]){
                dis[i]=mp[v][i]-mid*w[v][i];
            }
        }
    }
    return sum>=0;
}

int main(){

    int n;
    while(scanf("%d", &n), n){

        for(int i=1; i<=n; i++){
            scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);
        }
        for(int i=1; i<=n; i++){
            for(int j=i+1; j<=n; j++){
                mp[i][j]=abs((int)(z[i]-z[j]));
                mp[j][i]=abs((int)(z[i]-z[j]));
                w[i][j]=w[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            }
        }
        double L=0, R=(1ll<<30);
        for(int i=1; i<=50; i++){
            double mid=(L+R)/2;
            if(check(mid, n)){
                L=mid;
            }
            else{
                R=mid;
            }
        }
        printf("%.3f\n", R);
    }

    return 0;
}