题目描述：

给你n个水库，告诉你每个水库的xy坐标（米）和这个水库的花费。

如果两个水库需要连接，连接的费用是这两个水库的高度差的绝对值。

让你连接一些水库，让所有的水库都能到达1号水库并且只有一条通路（就是一棵树）。

然你使每米的花费最少（就是总花费 比 总长度）

解题报告：

题目大意是给一些点，这些点两两之间有距离，有代价。请你找出一个最小生成树，

使代价/距离最小。

最优比率生成树问题。

若记代价/距离为r，则http://s11/middle/64675f5448f46650227c1&690PKU 2728 最优比率生成树 二分" TITLE="POJ PKU 2728 最优比率生成树 二分" />，其中Xi=0或1，表示取不取i这条边。

记http://s6/middle/64675f5448f4498a52d15&690PKU 2728 最优比率生成树 二分" TITLE="POJ PKU 2728 最优比率生成树 二分" />，则Z(r)=0时，r为解（注意这个式子怎么变来的）。

那么我们将边权变为http://s7/middle/64675f5448f4499d79956&690PKU 2728 最优比率生成树 二分" TITLE="POJ PKU 2728 最优比率生成树 二分" />求生成树，如果Z(r)=0，则r就是我们的解。

至于怎么逼近r，推荐用Dinkelbach(迭代法)，不用二分法。二分法慢，且初始上下界太容易出现问题。而Dinkelbach随意取初值即可。

我用的二分。

代码如下：

#include<iostream>
#include<cmath>
using namespace std;
#define size 1000
#define eps 1e-8
#define Max 0x7fffffff
struct pint
{
    int x, y, z;
}v[size];
double g[size][size], d[size];
bool vst[size];
int n;
double prim()
{
    for(int i = 1; i < n; i++) d[i] = g[0][i];
    memset(vst, 0, sizeof(bool) * n); vst[0] = 1;
    double ans = 0;
    for(int k = 1; k < n; k++)
    {
        int id = -1;
        double mmin;
        for(int i = 1; i < n; i++)
            if (!vst[i] && (id == -1 || d[i] < mmin))
            {
                mmin = d[i];
                id = i;
            }
        ans += mmin; vst[id] = 1;
        for(int i = 1; i < n; i++)
            if (!vst[i] && g[id][i] < d[i])
                d[i] = g[id][i];
    }
    return ans;
}
int main()
{
    while(scanf("%d", &n) && n)
    {
        for(int i = 0; i < n; i++)
            scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].z);
        double l = 0, r = 1000000;
        while(r - l >= eps)
        {
            double mid = (r + l) * 0.5;
            for(int i = 0; i < n; i++) g[i][i] = pow(10.0, 12.0);
            for(int i = 0; i < n; i++)
                for(int j = i + 1; j < n; j++)
                    g[i][j] = g[j][i] = -mid * sqrt(1.0 * (v[i].x - v[j].x) * (v[i].x - v[j].x) + (v[i].y - v[j].y) * (v[i].y - v[j].y)) + fabs(1.0 * (v[i].z - v[j].z));
            double tmp = prim();
            if (tmp <= -eps) r = mid;
            else l = mid;
        }
        printf("%.3f\n", l);
    }
    return 0;
}