题意：大卫大帝刚刚建立了一个沙漠帝国，为了赢得他的人民的尊重，他决定在全国各地建立渠道，为每个村庄提供水源。与首都相连的村庄将得到水资源的浇灌。他希望构建的渠道可以实现单位长度的平均成本降至最低。换句话说，渠道的总成本和总长度的比值能够达到最小。他只希望建立必要的渠道，为所有的村庄提供水资源，这意味着每个村庄都有且仅有一条路径连接至首都。他的工程师对所有村庄的地理位置和高度都做了调查，发现所有渠道必须直接在两个村庄之间水平建造。由于任意两个村庄的高度均不同，所以每个渠道都需要安装一个垂直的升降机，从而使得水能够上升或下降。建设渠道的成本只跟升降机的高度有关，换句话说只和渠道连接的两个村庄的高度差有关。需注意，所有村庄（包括首都）的高度都不同，不同渠道之间不能共享升降机。

输入：输入包含多组测试数据。每组测试数据第一行包含整数N，表示村庄（包括首都）的总数目。接下来 NN 行，每行包含三个整数 x,y,zx,y,z，描述一个村庄的地理位置，(x,y)(x,y) 为该村庄的位置坐标，zz 为该村庄的地理高度。第一个被描述的村庄即为首都。当输入一行为 00 时，表示输入终止。

一句话题意：一个 NN 个点 MM 条边的无向图，每条边 ee 都有一个收益 CeC_e 和成本 ReR_e ，求该图的一个生成树 TT，使树中各边收益之和除以成本之和，即 ∑e∈TCe∑e∈TRe\frac{\sum_{e\in T}C_e}{\sum_{e\in T}R_e} 最大。

这是一道经典的最优比率生成树问题，同时也是 0101 分数规划的一道运用题。

直接选择二分答案，设当前二分的值为 midmid，根据 0101 分数规划原理，只需要构建一张新的无向图，图中每条边的权值为 Ce−mid×ReC_e-mid\times R_e 。在新的无向图中求最大生成树，如果最大生成树的边权之和非负，说明可行，令 l=midl=mid，否则令 r=midr=mid。

二分结束时，(l+r)/2(l+r)/2 即为答案。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n;
double eps=1e-6,vis[1010],dis[1010];
double minn=1e9,maxx;
struct city
{
	double x;
	double y;
	double z;
}s[1010];
double num(int i,int j,double x)
{
	return fabs(s[i].z-s[j].z)-x*sqrt((s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y));
}//图上的权值
double prim(double x)
{
	int u,last;
	double ans=0;
	double minn;
	memset(vis,0,sizeof(vis));
	vis[1]=1;
	dis[1]=0;
	u=1;
	for(int i=2;i<=n;i++)
		dis[i]=0x3f3f3f3f;
	for(int i=1;i<n;i++)
	{
		minn=0x3f3f3f3f;
		last=0;
		for(int j=1;j<=n;j++)
		{
			if(vis[j])
				continue;
			dis[j]=min(dis[j],num(u,j,x));
			if(minn-dis[j]>=eps)
			{
				minn=dis[j];
				last=j;
			}
		}
		ans+=minn;
		vis[last]=1;
		u=last;
	}
	return ans;//求最大生成树
}
int main()
{
	while(scanf("%d",&n)!=EOF&&n)
	{
		memset(s,0,sizeof(s));
		minn=1e9;
		maxx=0.0;
		for(int i=1;i<=n;i++)
		{
			scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].z);
			minn=min(minn,s[i].z);
			maxx=max(maxx,s[i].z);
		}
		double l=0,r=maxx-minn,mid;
		while(r-l>eps)
		{
			mid=(l+r)/2.0;
			double p=prim(mid);
			if(fabs(p)<eps)
				break;
			if(p>=0)//判断是否大于0
				l=mid;
			else
				r=mid;
		}
		printf("%.3lf\n",mid);
	}
    return 0;
}