#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
题意整理;原题与输入输出格式对照。
每个村庄有平面坐标 (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
题意整理;原题与输入输出格式对照。