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

最优比率生成树教程见http://blog.csdn.net/sdj222555/article/details/7490797

个人觉得很明白易懂，但他写的代码略囧。

模板题，但是必须Prim，不能用Kruscal，因为是完全图

Code:

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 struct Point{double x,y,h;}p[];

 int n;

 bool vis[];

 double DIS[][],H[][],map[][],minn[]/*minn[i]存放蓝点i与白点相连的最小边权*/;

 inline double sqr(const double &x){return x*x;}

 inline double dis(const Point &a,const Point &b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}

 inline double prim(const double &rate)

 {

     double sum=;

     for(int i=;i<=n;i++)

       for(int j=;j<=n;j++)

         map[i][j]=H[i][j]-DIS[i][j]*rate;//重设边权

     memset(vis,false,sizeof(vis));

     memset(minn,0x7f,sizeof(minn));

     minn[]=;

     for(int i=;i<=n;i++)

       {

         int v=;

         for(int j=;j<=n;j++)

           if(!vis[j]&&minn[j]<minn[v])

             v=j;

         vis[v]=true;

         for(int j=;j<=n;j++)

           if(!vis[j])

             minn[j]=min(minn[j],map[v][j]);

       }

     for(int i=;i<=n;i++)

       sum+=minn[i];

     return sum;

 }

 int main()

 {

     while()

       {

           scanf("%d",&n);

           if(!n)

             break;

           for(int i=;i<=n;i++)

             scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].h);

           for(int i=;i<=n;i++)

             for(int j=;j<=n;j++)

               {

                 DIS[i][j]=dis(p[i],p[j]);

                 H[i][j]=fabs(p[i].h-p[j].h);

               }

           double l=0.0,r=100.0;

           while(r-l>0.0000001)//二分比率

             {

                 double m=(l+r)/;

                 if(prim(m)>=)

                   l=m;

                 else

                   r=m;

             }

           printf("%.3f\n",r);

       }

     return ;

 }