题目大意：给定一个 N 个点的无向完全图，边有两个不同性质的边权，求该无向图的一棵最优比例生成树，使得性质为 A 的边权和比性质为 B 的边权和最小。

题解：要求的答案可以看成是 0-1 分数规划问题，即：选定一个数 mid，每次重新构建边权为 \(a[i]-mid*b[i]\) 的图，再在图上跑一遍最小生成树（这里由于是完全图，应该采用 Prim 算法）判断最小值和给定判定的最小值的关系即可，这里为：若最小值大于 mid，则下界提高，否则上界下降。

代码如下

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=1010;

const double eps=1e-5;

int n;bool vis[maxn];

double cost[maxn][maxn],d[maxn][maxn],mp[maxn][maxn],x[maxn],y[maxn],h[maxn],mx,s[maxn];

inline double calc(int i,int j){

	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

}

void read_and_parse(){

	for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&x[i],&y[i],&h[i]);

	for(int i=1;i<=n;i++)

		for(int j=i+1;j<=n;j++){

			cost[i][j]=cost[j][i]=fabs(h[i]-h[j]);

			d[i][j]=d[j][i]=calc(i,j);

			mx=max(mx,cost[i][j]/d[i][j]);

		}

}

double prim(){

	fill(vis+1,vis+n+1,0);

	double res=0;

	s[1]=0,vis[1]=1;

	for(int i=1;i<=n;i++)s[i]=mp[1][i];

	for(int i=1;i<n;i++){

		int u=0;

		for(int j=1;j<=n;j++)if(!vis[j]&&(!u||s[j]<s[u]))u=j;

		vis[u]=1,res+=s[u];

		for(int v=1;v<=n;v++)if(!vis[v])s[v]=min(s[v],mp[u][v]);

	}

	return res;

}

bool check(double mid){

	for(int i=1;i<=n;i++)

		for(int j=i+1;j<=n;j++)

			mp[i][j]=mp[j][i]=cost[i][j]-mid*d[i][j];

	return prim()>0;

}

void solve(){

	double l=0,r=mx;

	while(r-l>eps){

		double mid=(l+r)/2.0;

		if(check(mid))l=mid;

		else r=mid;

	}

	printf("%.3lf\n",l);

}

int main(){

	while(scanf("%d",&n)&&n){

		read_and_parse();

		solve();

	}

	return 0;

}