[POJ2728]Desert King（01分数规划）

2019-11-08 19:44:09

字体：大中小

来源：转载

供稿：网友

题目描述

传送门题意：给出n个点的坐标和海拔，两个点之间的距离为欧氏距离，花费为海拔差，求一个生成树，满足每公里的花费最小

题解

一个裸的最优比率生成树问题二分R，然后每条边权记为di=costi−R∗leni $d_i=cost_i-R*len_i$ 然后求一个最小生成树，如果边权和小于0说明有更优解

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 1005const double eps=1e-6;int dcmp(double x){ if (x<=eps&&x>=-eps) return 0; return (x>0)?1:-1;}int n;double ans;double x[N],y[N],h[N],a[N][N],b[N][N],d[N][N],minn[N];bool vis[N];double check(double R){ memset(minn,127,sizeof(minn));minn[1]=0; memset(vis,0,sizeof(vis)); for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) d[i][j]=a[i][j]-R*b[i][j]; for (int i=1;i<=n;++i) { int k=0; for (int j=1;j<=n;++j) if (!vis[j]&&minn[j]<minn[k]) k=j; vis[k]=1; for (int j=1;j<=n;++j) if (!vis[j]&&d[k][j]<minn[j]) minn[j]=d[k][j]; } double re=0; for (int i=1;i<=n;++i) re+=minn[i]; return re;}double find(){ double l=0.0,r=1e7,mid,now,ans=1e7; while (dcmp(r-l)>0) { mid=(l+r)/2.0; now=check(mid); if (dcmp(now)<0) ans=r=mid; else l=mid; } return ans;}int main(){ while (~scanf("%d",&n)) { if (!n) break; for (int i=1;i<=n;++i) scanf("%lf%lf%lf",&x[i],&y[i],&h[i]); if (n==1) {puts("0.000");continue;} for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) { a[i][j]=fabs(h[i]-h[j]); b[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); } ans=find(); PRintf("%.3lf/n",ans); }}

上一篇：activiti工作流的web流程设计器整合视频教程 SSM和独立部署

下一篇：[POJ2976]Dropping tests（01分数规划）