【POJ2728】Desert King 最优比率生成树

题目大意:给定一个 N 个点的无向完全图,边有两个不同性质的边权,求该无向图的一棵最优比例生成树,使得性质为 A 的边权和比性质为 B 的边权和最小。

题解:要求的答案可以看成是 0-1 分数规划问题,即:选定一个数 mid,每次重新构建边权为 \(a[i]-mid*b[i]\) 的图,再在图上跑一遍最小生成树(这里由于是完全图,应该采用 Prim 算法)判断最小值和给定判定的最小值的关系即可,这里为:若最小值大于 mid,则下界提高,否则上界下降。

代码如下

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1010;
const double eps=1e-5; int n;bool vis[maxn];
double cost[maxn][maxn],d[maxn][maxn],mp[maxn][maxn],x[maxn],y[maxn],h[maxn],mx,s[maxn]; inline double calc(int i,int j){
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
} void read_and_parse(){
for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&x[i],&y[i],&h[i]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
cost[i][j]=cost[j][i]=fabs(h[i]-h[j]);
d[i][j]=d[j][i]=calc(i,j);
mx=max(mx,cost[i][j]/d[i][j]);
}
} double prim(){
fill(vis+1,vis+n+1,0);
double res=0;
s[1]=0,vis[1]=1;
for(int i=1;i<=n;i++)s[i]=mp[1][i];
for(int i=1;i<n;i++){
int u=0;
for(int j=1;j<=n;j++)if(!vis[j]&&(!u||s[j]<s[u]))u=j;
vis[u]=1,res+=s[u];
for(int v=1;v<=n;v++)if(!vis[v])s[v]=min(s[v],mp[u][v]);
}
return res;
} bool check(double mid){
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
mp[i][j]=mp[j][i]=cost[i][j]-mid*d[i][j];
return prim()>0;
} void solve(){
double l=0,r=mx;
while(r-l>eps){
double mid=(l+r)/2.0;
if(check(mid))l=mid;
else r=mid;
}
printf("%.3lf\n",l);
} int main(){
while(scanf("%d",&n)&&n){
read_and_parse();
solve();
}
return 0;
}
上一篇:POJ 2728 Desert King 最优比率生成树


下一篇:生产环境中,数据库升级维护的最佳解决方案flyway