首页 > 代码库 > 【POJ】【2728】 Desert King 最优比率生成树
【POJ】【2728】 Desert King 最优比率生成树
题意:给出每个点的坐标(x,y,z),两点间距离是x,y的直线距离,边权为z差,求∑边权 / ∑距离 的最小值。
最优比率生成树!(分数规划)
就是根据分数规划的思想建树,每次看得到的总和是正是负。
二分代码:
#include<string.h> #include<stdio.h> #include<stdlib.h> #include<math.h> #define N 1010 typedef struct KSD { int x,y,z; }ksd; typedef struct LEONA { int cost; double len,rate; }leona; ksd s[N]; leona e[N][N]; double dist[N]; int v[N],n; int jkl(double ans) { int i,j,k; dist[1]=0; memset(v,0,sizeof(v)); for(i=2;i<=n;i++) { dist[i]=9999999.9; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { e[i][j].rate=e[i][j].cost-ans*e[i][j].len; } } for(ans=0,j=1;j<=n;j++) { int lord; double evil=9999999.9; for(i=1;i<=n;i++) { if(v[i]==0&&dist[i]<evil) { lord=i; evil=dist[i]; } } v[lord]=1; ans+=evil; for(i=1;i<=n;i++) { if(v[i]==0&&dist[i]-0.000001>e[lord][i].rate) { dist[i]=e[lord][i].rate; } } } return ans-0.0000001<0?1:0; } int main() { int i,j,k; double l,r,mid; while(scanf("%d",&n),n) { for(i=1;i<=n;i++) { scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].z); } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { e[i][j].cost=abs(s[i].z-s[j].z); e[i][j].len=sqrt((double)(s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y)); } } l=0.0; r=100.0; for(i=1;i<=25;i++) { mid=(l+r)/2; if(jkl(mid)) { r=mid+0.0000001; } else { l=mid; } } printf("%.3lf\n",mid); } return 0; }
迭代代码:
#include<string.h> #include<stdio.h> #include<stdlib.h> #include<math.h> #define N 1010 typedef struct KSD { int x,y,z; }ksd; typedef struct LEONA { int cost; double len,rate; }leona; ksd s[N]; leona e[N][N]; double dist[N]; int v[N],f[N],n; double jkl(double ans) { int i,j,k; double maimeng,mai_xie; maimeng=mai_xie=0; dist[1]=0; memset(v,0,sizeof(v)); for(i=2;i<=n;i++) { dist[i]=9999999.9; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { e[i][j].rate=e[i][j].cost-ans*e[i][j].len; } } for(j=1;j<=n;j++) { int lord; double evil=9999999.9; for(i=1;i<=n;i++) { if(v[i]==0&&dist[i]<evil) { lord=i; evil=dist[i]; } } v[lord]=1; maimeng+=e[f[lord]][lord].cost; mai_xie+=e[f[lord]][lord].len; for(i=1;i<=n;i++) { if(v[i]==0&&dist[i]-0.000001>e[lord][i].rate) { dist[i]=e[lord][i].rate; f[i]=lord; } } } ans=maimeng/mai_xie; return ans; } int main() { // freopen("test.in","r",stdin); int i,j,k; double l,r,mid; while(scanf("%d",&n),n) { for(i=1;i<=n;i++) { scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].z); } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { e[i][j].cost=abs(s[i].z-s[j].z); e[i][j].len=sqrt((double)(s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y)); } } r=100.0; for(i=1;i<=25;i++) { r=jkl(r); } printf("%.3lf\n",r); } return 0; }
13250412 | 18357 | 2728 | Accepted | 23944K | 1704MS | C++ | 1468B | 2014-08-05 15:59:04 |
13249973 | 18357 | 2728 | Accepted | 23948K | 1672MS | C++ | 1406B | 2014-08-05 15:19:12 |
复制去Google翻译翻译结果
【POJ】【2728】 Desert King 最优比率生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。