poj2728 Desert King(最小生成树+01分数规划=最优比率生成树)
2024-08-31 12:43:37
题意
n个点完全图,每个边有两个权值,求分数规划要求的东西的最小值。
(n<=1000)
题解
心态炸了。
堆优化primT了。
普通的就过了。
我再也不写prim了!!!!
咳咳
最优比率生成树板子题。
公式不是很难推吧。
#include<iostream>
#include<cmath>
#include<iomanip>
#include<string.h>
const int N=;
const int inf=0x7fffffff;
using namespace std;
int n,book[N];
double x[N],y[N],h[N],w2[N][N],w1[N][N],ans,dis[N];
double prim(double mid){
double mn;
ans=;
memset(book,,sizeof(book));
int now;
for(int i=;i<=n;i++)
dis[i]=w2[][i]-w1[][i]*mid;
for(int i=;i<=n;i++){
mn=inf;
for(int j=;j<=n;j++)
if(!book[j]&&mn>dis[j]){
now=j;
mn=dis[j];
}
book[now]=;
ans+=mn;
for(int j=;j<=n;j++)
if(!book[j]&&dis[j]>w2[now][j]-w1[now][j]*mid)
dis[j]=w2[now][j]-w1[now][j]*mid;
}
return ans;
}
double kf(int i,int j){
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main(){
while(scanf("%d",&n)&&n){
for(int i=;i<=n;i++){
scanf("%lf%lf%lf",&x[i],&y[i],&h[i]);
for(int j=;j<i;j++){
w1[i][j]=w1[j][i]=kf(i,j);
w2[i][j]=w2[j][i]=abs(h[i]-h[j]);
}
}
double l=0.0,r=1000.0,mid;
while(r-l>1e-){
mid=(l+r)/;
if(prim(mid)>=) l=mid;
else r=mid;
}
printf("%.3lf\n",l);
}
}
最新文章
- .NET4.5 WFP中用WebBrowser获取/操作网页html代码
- Android HandlerThread 的使用及其Demo (转)
- 12.创建一个Point类,有成员变量x,y,方法getX(),setX(),还有一个构造方 法初始化x和y。创建类主类A来测试它。
- LinkedHashMap及其源码分析
- PHP获取当前日期和时间及格式化方法参数
- smarty入门
- 源码分析:Java对象的内存分配
- ps 使用说明
- JY游戏之毁经典《扫雷》
- node.js模拟qq漂流瓶
- uTenux&mdash;&mdash;HelloWord
- Android 对 properties文件的读写操作
- 使用inno setup打包程序完整脚本(.net框架检测,重复安装检测)
- Amazon Kinesis Producer Library 使用记录
- div 布局2
- Spring4.0学习笔记(4) —— 使用外部属性文件
- Java-高效地使用Exception-实践
- linux上安装redis的踩坑过程2
- Mycat的分库分表
- Codeforces Round #524 (Div. 2) C. Masha and two friends(思维+计算几何?)
热门文章
- Java8 方法引用与构造器引用,数组引用
- SpringBoot(二) 主程序详解和配置文件如何配置
- 学习es6 setter/getter研究
- (转载)Android:学习AIDL,这一篇文章就够了(上)
- AOP为Aspect Oriented Programming的缩写,意为:面向切面编程
- BZOJ 4199: [Noi2015]品酒大会 后缀自动机_逆序更新
- PHP检验代码执行效率—时间统计方法
- svn 验证位置失败 Authorization failed
- U盘安装CentOS 7系统
- 洛谷 P1220 关路灯 (贪心+区间dp)