首页 > 代码库 > poj 2718 最优比例生成树(01分数规划)模板
poj 2718 最优比例生成树(01分数规划)模板
/* 迭代法 :204Ms */ #include<stdio.h> #include<string.h> #include<math.h> #define N 1100 #define eps 1e-10 #define inf 0x3fffffff struct node { int u,v,w; }p[N]; double ma[N][N]; double distance(int i,int j) { return sqrt(1.0*(p[i].u-p[j].u)*(p[i].u-p[j].u)+1.0*(p[i].v-p[j].v)*(p[i].v-p[j].v)); } int n; double prime(int u,double r) { int i,j,vis[N],pre[N]; double dis[N],len=0,cost=0,total=0; for(i=1;i<=n;i++) { dis[i]=fabs(1.0*p[u].w-1.0*p[i].w)-ma[u][i]*r; pre[i]=u; } memset(vis,0,sizeof(vis)); vis[1]=1; for(i=1;i<n;i++) { double minn=inf; int index=-1; for(j=1;j<=n;j++) if(!vis[j]&&minn>dis[j]) { minn=dis[j]; index=j; } if(index!=-1) { vis[index]=1; len+=ma[pre[index]][index]; cost=cost+fabs(1.0*p[pre[index]].w-1.0*p[index].w); //total+=dis[index]; for(j=1;j<=n;j++) { double f=fabs(1.0*p[index].w-1.0*p[j].w)-ma[index][j]*r; if(!vis[j]&&f<dis[j]) { dis[j]=f; pre[j]=index; } } } } // return total; return cost/len; } int main() { int i,j; while(scanf("%d",&n),n) { for(i=1;i<=n;i++) scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w); for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) ma[i][j]=ma[j][i]=distance(i,j); /* double l=0.0,r=100.0; while(r-l>eps) { double mid=(l+r)/2; if(prime(1,mid)>=0)l=mid; else r=mid; }*/ double a=0,b; while(1) { b=prime(1,a); if(fabs(a-b)<eps)break; a=b; } //printf("%.3f\n",r); printf("%.3f\n",b); } return 0; }
/* 二分法:1766ms */ #include<stdio.h> #include<string.h> #include<math.h> #define N 1100 #define eps 1e-10 #define inf 0x3fffffff struct node { int u,v,w; }p[N]; double ma[N][N]; double distance(int i,int j) { return sqrt(1.0*(p[i].u-p[j].u)*(p[i].u-p[j].u)+1.0*(p[i].v-p[j].v)*(p[i].v-p[j].v)); } int n; double prime(int u,double r) { int i,j,vis[N],pre[N]; double dis[N],len=0,cost=0,total=0; for(i=1;i<=n;i++) { dis[i]=fabs(1.0*p[u].w-1.0*p[i].w)-ma[u][i]*r; pre[i]=u; } memset(vis,0,sizeof(vis)); vis[1]=1; for(i=1;i<n;i++) { double minn=inf; int index=-1; for(j=1;j<=n;j++) if(!vis[j]&&minn>dis[j]) { minn=dis[j]; index=j; } if(index!=-1) { vis[index]=1; // len+=ma[pre[index]][index]; //cost=cost+fabs(1.0*p[pre[index]].w-1.0*p[index].w); total+=dis[index]; for(j=1;j<=n;j++) { double f=fabs(1.0*p[index].w-1.0*p[j].w)-ma[index][j]*r; if(!vis[j]&&f<dis[j]) { dis[j]=f; pre[j]=index; } } } } return total; // return cost/len; } int main() { int i,j; while(scanf("%d",&n),n) { for(i=1;i<=n;i++) scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w); for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) ma[i][j]=ma[j][i]=distance(i,j); double l=0.0,r=100.0; while(r-l>eps) { double mid=(l+r)/2; if(prime(1,mid)>=0)l=mid; else r=mid; } /*double a=0,b; while(1) { b=prime(1,a); if(fabs(a-b)<eps)break; a=b; }*/ printf("%.3f\n",r); //printf("%.3f\n",b); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。