题意

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);
}
}

最新文章

  1. .NET4.5 WFP中用WebBrowser获取/操作网页html代码
  2. Android HandlerThread 的使用及其Demo (转)
  3. 12.创建一个Point类,有成员变量x,y,方法getX(),setX(),还有一个构造方 法初始化x和y。创建类主类A来测试它。
  4. LinkedHashMap及其源码分析
  5. PHP获取当前日期和时间及格式化方法参数
  6. smarty入门
  7. 源码分析:Java对象的内存分配
  8. ps 使用说明
  9. JY游戏之毁经典《扫雷》
  10. node.js模拟qq漂流瓶
  11. uTenux&mdash;&mdash;HelloWord
  12. Android 对 properties文件的读写操作
  13. 使用inno setup打包程序完整脚本(.net框架检测,重复安装检测)
  14. Amazon Kinesis Producer Library 使用记录
  15. div 布局2
  16. Spring4.0学习笔记(4) —— 使用外部属性文件
  17. Java-高效地使用Exception-实践
  18. linux上安装redis的踩坑过程2
  19. Mycat的分库分表
  20. Codeforces Round #524 (Div. 2) C. Masha and two friends(思维+计算几何?)

热门文章

  1. Java8 方法引用与构造器引用,数组引用
  2. SpringBoot(二) 主程序详解和配置文件如何配置
  3. 学习es6 setter/getter研究
  4. (转载)Android:学习AIDL,这一篇文章就够了(上)
  5. AOP为Aspect Oriented Programming的缩写,意为:面向切面编程
  6. BZOJ 4199: [Noi2015]品酒大会 后缀自动机_逆序更新
  7. PHP检验代码执行效率—时间统计方法
  8. svn 验证位置失败 Authorization failed
  9. U盘安装CentOS 7系统
  10. 洛谷 P1220 关路灯 (贪心+区间dp)