pku2728最簡單的最優比例生成樹。黑書上有類似的題目，只是推出的0-1分數規劃的式子不同，思想一樣：
MST + bisearch
目前問題是不知如何估計二分搜索的上下界，看discuss上都是卡上下界過的。
1 #include <iostream>
2 #include <math.h>
3 #define max(a,b) (a>b?a:b)
4 #define min(a,b) (a<b?a:b)
5 #define inf 1.5*100000000
6
7 using namespace std;
8
9 const int maxn=1001;
10 //int place[]
11 double G[maxn][maxn];
12 double dis[maxn][maxn];
13 double h[maxn];
14 int n;
15
16 double prim()
17 {
18 int i,j,k;
19 bool s[maxn];
20 double close[maxn];
21 memset(s,false,sizeof(s));
22 for(i=0;i<n;i++) close[i]=inf;
23 s[0]=1;
24 for(i=1;i<n;i++) close[i]=G[0][i];
25 double total=0;
26 for(i=1;i<n;i++){
27 int idx;
28 double mn=inf;
29 for(j=1;j<n;j++) if(!s[j] && close[j]<mn){
30 idx=j;
31 mn=close[j];
32 }
33 s[idx]=1;
34 total+=close[idx];
35 for(j=1;j<n;j++) if(!s[j] && close[j]>G[idx][j]) close[j]=G[idx][j];
36 }
37 return total;
38 }
39 // 給定當前比例r，建新圖
40 void buildG(double r)
41 {
42 int i,j,k;
43 for(i=0;i<n;i++) for(j=0;j<n;j++) G[i][j]=0;
44 //printf("G with r=%.3lf\n",r);
45 for(i=0;i<n;i++){
46 for(j=i+1;j<n;j++){
47 G[i][j]=G[j][i]=fabs(h[i]-h[j])-r*dis[i][j];
48 //printf("%.2lf ",G[i][j]);
49 }
50 //printf("\n");
51 }
52 // printf("\n");
53 }
54
55 void read()
56 {
57 int i,j;
58 double x[maxn],y[maxn];
59 //scanf("%d",&n);
60 for(i=0;i<n;i++){
61 scanf("%lf%lf%lf",&x[i],&y[i],&h[i]);
62 }
63 for(i=0;i<n;i++) dis[i][i]=0;
64 for(i=0;i<n;i++) for(j=i+1;j<n;j++){
65 dis[i][j]=dis[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
66 //printf("%d %d %.2lf\n",i,j,dis[i][j]);
67 }
68 }
69
70 void solve()
71 {
72 // discuss 里的上下界
73 double l=0,h=31,mid=(h+l)/2;
74 buildG(mid);
75 //printf("%.3lf\n",prim());
76
77 // 二分搜索r_star使得用r_star建立的圖的最小生成樹權為0
78
79 while(true){
80 double res=prim();
81 if(fabs(res)<1e-5) break;
82 if(res<0) h=mid;
83 else l=mid;
84 mid=(h+l)/2;
85 buildG(mid);
86 }
87
88 printf("%.3lf\n",mid);
89 }
90
91 int main()
92 {
93 while(scanf("%d",&n) && n!=0){
94 read();
95 solve();
96 }
97 }
98