[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();