题目大意呢。。。
很多村庄&&一个王堡，王堡有水，村庄没水，可以修水渠，
两地之间修水渠的价格就是两地海拔差，长度就是水平距离
要求总花费：总长度尽量小，且一个村庄只有一条连向王堡的路。。
规定1号就是王堡
输入多组数据
开头N
然后N个x y z，表示横坐标 纵坐标，海拔高
如果N=0输入结束~~
输出最小比率，保留三位小数。。
传说中楼爷25minAC的题目，，我果断花了一天的时间
改的天昏地暗，各种优化。。。
最后发现错误是%.3f与%.3lf的不同（想不清啊。。。。）
思路：
很明显的最优比率啊，，
PS：（最优比率生成树可参考我滴另一篇文章~~自认为还行~~）
附链接：http://blog.csdn.net/loriex/article/details/18980625
我们有两种做法：
1.题意也就是总长度：总花费尽量大，那么长度是价值，花费是价格，
可以直接套用我之前写的最优比率生成树的思路，最后只要输出答案的倒数~~
（PS：我写的是妥妥的超时了。。按理说应该不至于，，可能我太渣了。。。
）
不过由于%.3lf的缘故我写了又改成了第二种思路
2.只要理解了最优比率生成树的做法，，这道题也可以类似推出啊。。
我们假设花费=l*长度
然后边权=花费-mid*长度
然后为了使l尽量小，我们选择用最小生成树
（为什么用最小生成树？？可以参考我的另一篇文章讲最优比率生成树的，
根据那个为什么用最大生成树的相同思路可以得解）
然后不断2分就可以得解了。。。
由于%.3lf WA了很多次
所以我的代码几乎是高仿别人的。。。（为了找错。。。）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
#define INF 1000000000
#define MAX 1001
struct node
{
int x;
int y;
int z;
};
node vill[MAX];
double dista[MAX][MAX],hengh[MAX][MAX],map[MAX][MAX],minmap[MAX];
bool vis[MAX];
int n;
double dis(int a,int b)
{//计算ab之间的距离
return sqrt((vill[a].x-vill[b].x)*(vill[a].x-vill[b].x)+(vill[a].y-vill[b].y)*(vill[a].y-vill[b].y));
}
void init()
{
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d",&vill[i].x,&vill[i].y,&vill[i].z);
}
for (int i = 1; i <= n; i++)
for (int j = i+1; j <= n; j++)
{
dista[j][i] = dista[i][j] = dis(i,j);
hengh[j][i] = hengh[i][j] = abs(vill[i].z - vill[j].z);
}//hengh是海拔差，dista是长度
}
void create(double l)
{//建图
for (int i = 1; i <= n; i++)
for (int j = i+1; j <= n; j++)
{
map[j][i] = map[i][j] = hengh[i][j] - l * dista[i][j];
}
}
double prim(double dist[])
{//计算出最小生成树的权和
double ans =0;
for (int i =1; i <= n; i++)
{
dist[i] = INF,
vis[i] = false;
}
dist[1] =0;
while (1)
{
double mindist = INF;
int mini =-1;
for (int i = 1; i <= n; i++)
if (dist[i] < mindist &&!vis[i])
{
mindist = dist[i];
mini = i;
}
if (mini == -1 )
return ans;
vis[mini] =true;
ans += mindist;
for (int i = 1; i <= n; i++)
if (!vis[i] && map[mini][i] < dist[i])
dist[i] = map[mini][i];
}
}
int main()
{
while( scanf("%d",&n) && n > 0 )
{
init();
double l = 0, r = 1000000000;
while (r - l > 0.0001)
{
double mid = (l + r) /2;
create(mid);
double temp = prim(minmap);
if (temp >=0)
l = mid;
else
r = mid;
}//不断二分得解
printf("%.3f\n",l);
}
return 0;
}