pku2726最优比率生成树.txt

MST算法就是最小生成树算法！ 在ACM中这个应该是比较简单的一个算法！ 大家好好学习吧！

/*
David刚刚成为一个沙漠之国的国王。为了赢得民心，他决定建一个路网覆盖整个王国
以方便各个村庄去打水。村庄只要能连接到他的首都就能有水了。作为这个国家权利和智慧的象征，
他需要以一种更合理的方式来建设这些路。
经过几天的学习，他最终制订出了他的计划。他希望这些路每英里的平均花费最小。
换句话说，就是希望这些路的总成本和总长度的比值最小。他只需要建能让所有村庄的村民顺利打水的必经之路，
也就是说每个村庄只能有一条路通向首都。
他的工程师勘察了整个王国，记录了每个村庄的坐标和海拔。每条路连接两个村庄的路必须是一条直线，
并且是水平的。由于每个村庄都有不同的海拔，他们决定在每条路上建一个提水用的升降机，
每条路的长度是两个村庄的水平距离，而花费就是两个村庄的高度差。需要注意的是，每个村庄都有不同的高度，
不同的路不能共享他们的升降机。建设的这些路可以相交，而且没有超过两个村庄在同一条直线上。
作为国王David的首席科学家兼程序员，你被要求找出建设这些路的最优方案。
输入
多组数据，每组数据第一行是一个数字N(2<=N<=1000)，表示村庄的个数。接下来N行描述村庄，
每行有3个数字x,y,z(0 <= x, y < 10000, 0 <= z < 10000000)。
(x,y)表示这个村庄的坐标，z是这个村庄的海拔。第一个村庄是首都。N=0表示数据结束。
输出
每组数据输出一个小数，表示总成本和总长度的最小的比值（结果精确到小数点后3位）
*/
#include <iostream>
#include <math.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define inf 1.5*100000000 
using namespace std; 
const int maxn=1001;
double G[maxn][maxn];
double dis[maxn][maxn];
double h[maxn];
int n; 
double prim()
{
      int i,j;
      bool s[maxn];
      double close[maxn];
      memset(s,false,sizeof(s));
      for(i=0;i<n;i++) close[i]=inf;
      s[0]=1;
      for(i=1;i<n;i++) close[i]=G[0][i];
      double total=0;
     for(i=1;i<n;i++){
         int idx;
          double mn=inf;
         for(j=1;j<n;j++) if(!s[j] && close[j]<mn){
             idx=j;
              mn=close[j];
          }
         s[idx]=1;
         total+=close[idx];
         for(j=1;j<n;j++) if(!s[j] && close[j]>G[idx][j]) close[j]=G[idx][j];
     }
     return total;
}
// 给定当前比例r，建新图  
void buildG(double r)
{
     int i,j;
     for(i=0;i<n;i++) for(j=0;j<n;j++) G[i][j]=0;
     //printf("G with r=%.3lf\n",r);
     for(i=0;i<n;i++){
         for(j=i+1;j<n;j++){
             G[i][j]=G[j][i]=fabs(h[i]-h[j])-r*dis[i][j];
             //printf("%.2lf ",G[i][j]);
         }
         //printf("\n");
     }
//   printf("\n");
}
void read()
{
     int i,j;
     double x[maxn],y[maxn];
     //scanf("%d",&n);
     for(i=0;i<n;i++){
        scanf("%lf%lf%lf",&x[i],&y[i],&h[i]);
     }
     for(i=0;i<n;i++) dis[i][i]=0;
     for(i=0;i<n;i++) for(j=i+1;j<n;j++){
         dis[i][j]=dis[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
          //printf("%d %d %.2lf\n",i,j,dis[i][j]);
     }
} 
void solve()
{
     // discuss 里的上下界 
     double l=0,h=31,mid=(h+l)/2;
     buildG(mid);
     //printf("%.3lf\n",prim());
    
    // 二分搜索r_star使得用r_star建立的图的最小生成树权为0      
     while(true){
         double res=prim();
         if(fabs(res)<1e-5) break;
        if(res<0) h=mid;
        else l=mid;
        mid=(h+l)/2; 
        buildG(mid);
    }    
    printf("%.3lf\n",mid);
}
int main()
{
    while(scanf("%d",&n) && n!=0){
       read();
       solve();
   }
   return 0;
}