首页 > 代码库 > （最优比率生成树）POJ 2728 - Desert King
（最优比率生成树）POJ 2728 - Desert King
题意：
很多村子，村子有三维坐标的属性，现在要求一个生成树，使得总高度和总宽度比率最小。
分析：
很经典的题型，可以使用二分来做，这里引用红书上的【说明】。
二分答案，假设最小的答案为best，二分答案为ans，那么我们将每条边的边权变为wi-ui*ans，则：
ans<best时，求最小生成树得到的答案>0
ans=best时，求最小生成树得到的答案=0
ans>best时，求最小生成树得到的答案<0
这里使用prim算法check一下即可。
还有一种算法是迭代法，就是初设一个值，将这个值代进去算，得到更优的解，直至完全收敛。
速度比二分快，具体需要看题。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 6 using namespace std; 7 8 #define eps (1e-6) 9 const int inf=0x3f3f3f3f;10 const int maxn=1010;11 int n;12 13 double x[maxn];14 double y[maxn];15 double z[maxn];16 double dist[maxn][maxn];17 double high[maxn][maxn];18 19 int sgn(double x) {20 return x < -eps ? -1 : x > eps ? 1 : 0;21 }22 23 double lowc[maxn];24 bool vis[maxn];25 26 double dis(double x1,double y1,double x2,double y2) {27 return sqrt(pow(x1-x2,2)+pow(y1-y2,2));28 }29 30 double check(double r) {31 double ans=0;32 memset(vis,false,sizeof(vis));33 vis[0]=true;34 for(int i=1; i<n; i++) {35 lowc[i]=high[0][i]-dist[0][i]*r;36 }37 for(int i=1; i<n; i++) {38 double minc=inf;39 int p=-1;40 for(int j=0; j<n; j++) {41 if(!vis[j]&&lowc[j]<minc) {42 minc=lowc[j];43 p=j;44 }45 }46 ans+=minc;47 vis[p]=true;48 for(int j=0; j<n; j++) {49 double d = high[p][j]-dist[p][j]*r;50 if(!vis[j]&&lowc[j]>d) {51 lowc[j]=d;52 }53 }54 }55 return ans;56 }57 58 59 int main() {60 while(scanf("%d",&n)&&n) {61 for(int i=0; i<n; i++) {62 scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);63 }64 for(int i=0; i<n; i++) {65 for(int j=i+1; j<n; j++) {66 dist[i][j]=dist[j][i]=dis(x[i],y[i],x[j],y[j]);67 high[i][j]=high[j][i]=fabs(z[i]-z[j]);68 // printf("%f %f\n",dist[i][j],high[i][j]);69 }70 }71 double left=0;72 double right = 100;73 while(sgn(left-right)<0) {74 double mid = (left+right)/2;75 double res = check(mid);76 // printf("%f %f\n",mid,res);77 if(sgn(res)<0) {78 right=mid;79 } else if(sgn(res)>0) {80 left=mid;81 } else {82 break;83 }84 }85 printf("%.3f\n",(left+right)/2);86 }87 88 return 0;89 90 }
（最优比率生成树）POJ 2728 - Desert King
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。