现在的位置: 首页 > 综合 > 正文

poj 2728 Desert King（最优比例生成树）

2017年09月28日 ⁄ 综合 ⁄ 共 2191字 ⁄ 字号 小 中 大 ⁄ 评论关闭
分类： Algorithm-动态规划2013-07-25
13:30 233人阅读 评论(0) 收藏 举报
[cpp] view
plaincopy

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cmath>  
  4. #include <cstdlib>  
  5. #include <cstring>   
  6. #include <iomanip>  
  7. using namespace std;  
  8. const int maxn=1005;  
  9. const double eps=1e-6;  
  10. const double inf=0xffffffff;  
  11. struct node{  
  12.     double x,y,h;  
  13. }no[maxn];  
  14. int n;    
  15. bool visited[maxn];    
  16.    
  17. double weight[maxn][maxn],c[maxn][maxn],d[maxn][maxn];  
  18. double up,down;  
  19. double dis(node &a,node &b){  
  20.     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));  
  21. }  
  22. void creattree(int n,double r)  
  23. {  
  24.     for(int i=0;i<n;i++)  
  25.         for(int j=0;j<n;j++)  
  26.         {  
  27.             weight[i][j]=c[i][j]-r*d[i][j];  
  28.         }  
  29. }  
  30. void prime()  
  31. {  
  32.     up=0.0;down=0.0;  
  33.     memset(visited,0,sizeof(visited));  
  34.     int index;  
  35.     int pre[maxn];  
  36.     double dist[maxn];   
  37.     visited[1]=1;  
  38.     for(int i=0;i<n;i++)  
  39.     {  
  40.         dist[i]=weight[1][i];  
  41.         pre[i]=1;  
  42.     }  
  43.     for(int i=0;i<n;i++)  
  44.     {  
  45.         double mmimum=inf;  
  46.         for(int j=0;j<n;j++)  
  47.         {  
  48.             if(!visited[j]&&dist[j]<mmimum)  
  49.             {  
  50.                 mmimum=dist[j];  
  51.                 index=j;  
  52.             }  
  53.         }  
  54.         visited[index]=1;  
  55.         up+=c[pre[index]][index];  
  56.         down+=d[pre[index]][index];  
  57.         for(int i=0;i<n;i++)  
  58.         {  
  59.             if(!visited[i]&&weight[index][i]<dist[i])  
  60.             {  
  61.                 dist[i]=weight[index][i];  
  62.                 pre[i]=index;  
  63.             }  
  64.         }  
  65.     }  
  66.       
  67. }  
  68. int main()  
  69. {     
  70.     while(scanf("%d",&n),n)  
  71.     {  
  72.         for(int i=0;i<n;i++)  
  73.         {     
  74.             scanf("%lf%lf%lf",&no[i].x,&no[i].y,&no[i].h);  
  75.         }  
  76.         for(int i=0;i<n;i++)  
  77.             for(int j=0;j<n;j++)  
  78.             {  
  79.                 c[i][j]=fabs(no[i].h-no[j].h);  
  80.                 d[i][j]=dis(no[i],no[j]);  
  81.             }  
  82.         double r=30.0,ans=30.0;  
  83.         while(1)  
  84.         {  
  85.             creattree(n,r);  
  86.             prime();  
  87.             r=up/down;  
  88.             if(fabs(r-ans)<=eps)break;  
  89.             else ans=r;  
  90.         }     
  91.         printf("%.3lf\n",ans);  
  92.         //cout<<fixed<<setprecision(3)<<ans<<endl;  
  93.           
  94.     }  
  95. }  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞