#256. 最优比率生成树

最优比率生成树

题目描述

每个村庄有平面坐标 (x,y) 和高度 h。连接两个村庄的长度为平面欧氏距离,费用为高度差的绝对值。构造一棵生成树,最小化总费用与总长度的比值。

输入格式

多组数据。每组先输入村庄数 n,再输入 n 行 x、y、h。n=0 结束。

输出格式

每组输出最优比值,保留三位小数。

样例输入

4
0 0 0
0 1 1
1 1 2
1 0 3
0

样例输出

1.000

题意整理;原题与输入输出格式对照。