题意：
图中每条边有两个权值(cost,len)，求其一棵生成树，使sum(cost)/sum(len)最小。
分析：
转化为求边权为s0*len-cost的最大生成树+牛顿迭代。s0为具有单调性迭代系数。
代码：
//poj 2728
//sep9
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
const int maxN=1024;
struct P
{int x,y,z;
}v[maxN];int cost[maxN][maxN];
double len[maxN][maxN];
double dis[maxN];
vector<int> g[maxN];
int vis[maxN];
int prev[maxN];
double s0,s1;
int n;double get_v()
{int sum_cost=0;double sum_len=0;for(int i=0;i<n;++i)if(g[i].size()){int j=g[i][0];sum_cost+=cost[i][j];sum_len+=len[i][j];}return sum_cost/sum_len;
}void prim()
{for(int i=0;i<n;++i)g[i].clear();for(int i=0;i<n;++i)dis[i]=-1e12; dis[0]=0;memset(vis,0,sizeof(vis));for(int t=0;t<n;++t){double maxx=-1e12;int maxi=-1;for(int i=0;i<n;++i){if(vis[i]==0&&dis[i]>maxx){maxi=i;maxx=dis[i];}} vis[maxi]=1;for(int i=0;i<n;++i)if(vis[i]==0)if(s0*len[maxi][i]-cost[maxi][i]>=dis[i]){dis[i]=s0*len[maxi][i]-cost[maxi][i];prev[i]=maxi;} }for(int i=1;i<n;++i)g[i].push_back(prev[i]);
}int main()
{while(scanf("%d",&n)==1&&n){for(int i=0;i<n;++i)scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].z); for(int i=0;i<n;++i)for(int j=i+1;j<n;++j){double dx=(v[i].x-v[j].x)*1.0;double dy=(v[i].y-v[j].y)*1.0;len[i][j]=len[j][i]=sqrt(dx*dx+dy*dy);cost[i][j]=cost[j][i]=abs(v[i].z-v[j].z);}for(int i=0;i<n;++i) g[i].clear();for(int i=0;i<n-1;++i)g[i].push_back(i+1);s0=get_v();while(1){prim();s1=get_v();if(fabs(s0-s1)<1e-5)break; s0=s1;} printf("%.3lf\n",s0+1e-9);}return 0;
}