poj2728 发表于 2018-11-01 | 分类于 题解 | 阅读数 次 链接:poj2728 题解 实际上求,T是一个生成树 显然是个01分数规划,确定一个之后将赋为边权,跑一边最小生成树就可以 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e3+7;const double esp=1e-5;struct node{int x,y,z;}mp[N];double a[N][N],b[N][N],c[N][N],dis[N];int n,vis[N];inline void init(){ rep(i,1,n)scanf("%d%d%d",&mp[i].x,&mp[i].y,&mp[i].z); rep(i,1,n)rep(j,i+1,n){ a[i][j]=a[j][i]=abs(mp[i].z-mp[j].z); b[i][j]=b[j][i]=sqrt(1.0*(mp[i].x-mp[j].x)*(mp[i].x-mp[j].x)+1.0*(mp[i].y-mp[j].y)*(mp[i].y-mp[j].y)); }}double check(double x){ double res=0; memset(vis,0,sizeof vis); rep(i,1,n)rep(j,i+1,n)c[i][j]=c[j][i]=a[i][j]-x*b[i][j]; rep(i,1,n)dis[i]=c[1][i]; vis[1]=1; rep(i,2,n){ int k; double mn=1.0*0x3f3f3f3f; rep(j,1,n)if(!vis[j]&&mn>dis[j]){mn=dis[j];k=j;} res+=mn;vis[k]=1; rep(j,1,n)if(!vis[j]&&dis[j]>c[k][j])dis[j]=c[k][j]; } return res;}double find(){ double l=0,r=1.0*0x3f3f3f3f; while(l+esp<r){ double mid=(l+r)/2; if(check(mid)<=0)r=mid; else l=mid; } return l;}int main(){ while(~scanf("%d",&n)&&n){ init(); double ans=find(); printf("%.3f\n",ans); } return 0;}