【最优比率生成树】poj2728 Desert King

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 struct Point{double x,y,h;}p[1001];
 7 int n;
 8 bool vis[1001];
 9 double DIS[1001][1001],H[1001][1001],map[1001][1001],minn[1001]/*minn[i]存放蓝点i与白点相连的最小边权*/;
10 inline double sqr(const double &x){return x*x;}
11 inline double dis(const Point &a,const Point &b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
12 inline double prim(const double &rate)
13 {
14     double sum=0;
15     for(int i=1;i<=n;i++)
16       for(int j=1;j<=n;j++)
17         map[i][j]=H[i][j]-DIS[i][j]*rate;//重设边权 
18     memset(vis,false,sizeof(vis));
19     memset(minn,0x7f,sizeof(minn));
20     minn[1]=0;
21     for(int i=1;i<=n;i++)
22       {
23         int v=0;
24         for(int j=1;j<=n;j++)
25           if(!vis[j]&&minn[j]<minn[v])
26             v=j;
27         vis[v]=true;
28         for(int j=1;j<=n;j++)
29           if(!vis[j])
30             minn[j]=min(minn[j],map[v][j]);
31       }
32     for(int i=1;i<=n;i++)
33       sum+=minn[i];
34     return sum;
35 }
36 int main()
37 {
38     while(1)
39       {
40           scanf("%d",&n);
41           if(!n)
42             break;
43           for(int i=1;i<=n;i++)
44             scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].h);
45           for(int i=1;i<=n;i++)
46             for(int j=1;j<=n;j++)
47               {
48                 DIS[i][j]=dis(p[i],p[j]);
49                 H[i][j]=fabs(p[i].h-p[j].h);
50               }
51           double l=0.0,r=100.0;
52           while(r-l>0.0000001)//二分比率 
53             {
54                 double m=(l+r)/2;
55                 if(prim(m)>=0)
56                   l=m;
57                 else
58                   r=m;
59             }
60           printf("%.3f\n",r);
61       }
62     return 0;
63 }