显然的0/1分数规划问题，用二分来解决，检验mid，就用prim算法求最小生成树，看总边权是否大等于0即可验证。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int M=1006;
4 const double eps=1e-8;
5 struct node{
6 double x,y,z;
7 }p[M];
8 double a[M][M],c[M][M];
9 bool v[M];
10 double d[M];
11 int n;
12
13 double dist(int i,int j){
14 return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
15 }
16
17 bool ck(double b){
18 double ans=0;
19 for(int i=0;i<=n+1;i++) d[i]=1e18;
20 memset(v,0,sizeof(v));
21 d[1]=0;
22 for(int i=1;i<=n;i++){
23 int x=0;
24 for(int j=1;j<=n;j++)
25 if(!v[j]&&(x==0||d[j]<d[x])) x=j;
26 v[x]=1;
27 ans+=d[x];
28 for(int j=1;j<=n;j++)
29 if(!v[j]) d[j]=min(d[j],c[x][j]-b*a[x][j]);
30 }
31 if(ans+eps>=0) return true;
32 return false;
33 }
34
35 int main(){
36 while(cin>>n&&n){
37 for(int i=1;i<=n;i++){
38 double x,y,z;
39 cin>>x>>y>>z;
40 p[i]=(node){x,y,z};
41 }
42 for(int i=1;i<=n;i++)
43 for(int j=i+1;j<=n;j++){
44 a[i][j]=a[j][i]=dist(i,j);
45 c[i][j]=c[j][i]=abs(p[i].z-p[j].z);
46 }
47 double l=0,r=1e8;
48 while(l+eps<r){
49 double mid=(l+r)/2.0;
50 if(ck(mid)) l=mid;
51 else r=mid;
52 }
53 printf("%.3lf\n",l);
54 }
55 return 0;
56 }
