题意分析

给定 $N$ 个带有平面坐标和海拔的村庄，首都为第 $1$ 个村庄。需要构造一棵生成树，使得树中每条边的“竖直水泵高度”（海拔差的绝对值）总和 $C$ 与所有边的水平距离总和 $L$ 之比 $\frac{C}{L}$ 最小。

解题思路

1. 二分答案：设目标比值为 $R$，判断能否构造一棵生成树使得 $\sum(\Delta z - R \cdot d)\le0$ 其中 $\Delta z$ 是每条边的海拔差绝对值，$d$ 是水平距离。
2. 编写检查函数：对给定 $R$，构造带权无向完全图，每条边的“改造权重” $w_{ij} = |\!z_i - z_j| - R\cdot\text{dist}((x_i,y_i),(x_j,y_j)).$ 在该图上用 Prim 算法求最小生成树，计算所有选边权重之和 $\sum w_{ij}$，若 $\sum w_{ij}\le0$ 则存在比 $R$ 更小的平均值。
3. 二分区间：根据题目限制，水泵高度与距离的比例在 $[0,100]$ 范围内都能搜到答案，设误差上限 $\varepsilon=10^{-6}$，二分至区间足够小后输出。

本题代码

#include <bits/stdc++.h>
using namespace std;

int n;
int x[1005], y[1005], z[1005];
double dis[1005][1005], cost[1005][1005];
double dval[1005];
bool vis[1005];

double cal_dis(int x1,int y1,int x2,int y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

bool prim(double R){
    for(int i=1;i<=n;i++){
        dval[i]=cost[1][i]-dis[1][i]*R;
        vis[i]=false;
    }
    dval[1]=0; vis[1]=true;
    for(int i=1;i<n;i++){
        int u=0;
        for(int j=1;j<=n;j++){
            if(!vis[j] && (u==0 || dval[j]<dval[u])) u=j;
        }
        vis[u]=true;
        for(int v=1;v<=n;v++){
            if(!vis[v])
                dval[v]=min(dval[v], cost[u][v]-dis[u][v]*R);
        }
    }
    double sum=0;
    for(int i=1;i<=n;i++) sum+=dval[i];
    return sum<=0;
}

int main(){
    const double EPS=1e-6;
    while(scanf("%d",&n)==1 && n){
        for(int i=1;i<=n;i++)
            scanf("%d %d %d",&x[i],&y[i],&z[i]);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dis[i][j]=cal_dis(x[i],y[i],x[j],y[j]);
                cost[i][j]=fabs(z[i]-z[j]);
            }
        }
        double l=0, r=100, mid;
        while(r-l>EPS){
            mid=(l+r)/2;
            if(prim(mid)) r=mid;
            else l=mid;
        }
        printf("%.3f\n", r);
    }
    return 0;
}