题面
大卫大帝刚刚建立了一个沙漠帝国，为了赢得他的人民的尊重，他决定在全国各地建立渠道，为每个村庄提供水源。
与首都相连的村庄将得到水资源的浇灌。
他希望构建的渠道可以实现单位长度的平均成本降至最低。
换句话说，渠道的总成本和总长度的比值能够达到最小。
他只希望建立必要的渠道，为所有的村庄提供水资源，这意味着每个村庄都有且仅有一条路径连接至首都。
他的工程师对所有村庄的地理位置和高度都做了调查，发现所有渠道必须直接在两个村庄之间水平建造。
由于任意两个村庄的高度均不同，所以每个渠道都需要安装一个垂直的升降机，从而使得水能够上升或下降。
建设渠道的成本只跟升降机的高度有关，换句话说只和渠道连接的两个村庄的高度差有关。
需注意，所有村庄（包括首都）的高度都不同，不同渠道之间不能共享升降机。
输入格式
输入包含多组测试数据。
每组测试数据第一行包含整数N，表示村庄（包括首都）的总数目。
接下来N行，每行包含三个整数x，y，z，描述一个村庄的地理位置，(x,y)为该村庄的位置坐标，z为该村庄的地理高度。
第一个被描述的村庄即为首都。
当输入一行为0时，表示输入终止。
输出格式
每组数据输出一个结果，每个结果占一行。
结果为一个保留三位小数的实数，表示渠道的总成本和总长度的比值的最小值。
数据范围
2≤N≤1000,
0≤x,y<10000,
0≤z≤10000000
输入样例：
4
0 0 0
0 1 1
1 1 2
1 0 3
0
输出样例：
1.000
题解
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define sqr(n) ((n)*(n))
using namespace std;
const int maxn = 1e3 + 5;
const double eps = 1e-6;
struct node{ int x,y,z; };
int n, v[maxn];
vector<node> ve;
double ans, e[maxn][maxn], dis[maxn];
void prim(double x)
{
rep (i, 1, n)
{
double mi = 2e9;
int now;
rep (j, 0, n - 1)
if(!v[j] && dis[j] < mi) mi = dis[j], now = j;
v[now] = 1;
ans += dis[now];
rep (j, 0, n - 1)
dis[j] = min(dis[j], abs(ve[now].z - ve[j].z) - x * e[now][j]);
}
}
bool judge(double x)
{
rep (i, 0, n - 1) dis[i] = 2e9, v[i] = 0;
dis[0] = 0; ans = 0;
prim(x);
return ans > 0;
}
int main()
{
while (cin >> n, n)
{
vector<node>().swap(ve);
for (int i = 1, x, y, z; i <= n; ++i)
{
cin >> x >> y >> z;
ve.emplace_back(node{x, y, z});
}
rep (i, 0, n - 1)
rep (j, 0, n - 1)
e[i][j] = sqrt(0.0 + sqr(ve[i].x - ve[j].x) + sqr(ve[i].y - ve[j].y));
double l = 0, r = 2e9;
while(r - l > eps)
{
double mid = (l + r) / 2;
if(judge(mid)) l = mid;
else r = mid;
}
printf("%0.3f
", r);
}
return 0;
}