思路

分数规划问题。我们可以求得每两个村子的距离和花费，然后列举最大的ans使得$\sum \mathrm{（}cos{t}_i-ans\ast le{n}_i\mathrm{）}=0\backslash sum\; （cost\_i-ans*len\_i）=0$

我们固定住1号作为根节点，只需要建一棵最小生成树，二分答案即可求出。

（每个点都是与最近的点连通取水，所以无需考虑从哪开始）

代码

#include<iostream>
#include<cstring>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e3+7;
const int mod=1e9+7;

int n,x[N],y[N],z[N],vis[N];
double dis[N],C[N][N],D[N][N];

double prim(int u,double k){ //MST+分数划分 
	memset(vis,0,sizeof(vis));
	int p=1;vis[u]=1;dis[1]=0;
	for(int i=2;i<=n;i++) dis[i]=C[u][i]-D[u][i]*k;
	double Min,ans=0;
	for(int i=2;i<=n;i++){
		Min=inf;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&dis[j]<Min){
				Min=dis[j];
				p=j;
			}
		vis[p]=1;
		ans+=dis[p];
		for(int j=1;j<=n;j++){
			double V=C[p][j]-D[p][j]*k;
			if(!vis[j]&&V<dis[j]) dis[j]=V;
 		}
	}
	return ans;
}

signed main(){
	while(cin>>n&&n){
		memset(D,0,sizeof(D));
		memset(C,0,sizeof(C)); 
		for(int i=1;i<=n;i++){
			cin>>x[i]>>y[i]>>z[i];
		}
		for(int i=1;i<n;i++){
			for(int j=i+1;j<=n;j++){
				D[i][j]=D[j][i]=sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]));
				C[i][j]=C[j][i]=abs(z[i]-z[j]);
			}
		}
		double l=0,r=100,mid;
		while(r-l>=1e-7){
			mid=(l+r)/2;
			if(prim(1,mid)>=0) l=mid;
			else r=mid;
		}
		printf("%.3lf\n",r);
	}
	return 0;
}