题目:

http://poj.org/problem?id=2728


题解:

二分比率,然后每条边边权变成w-mid*dis,用prim跑最小生成树就行

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 1005
using namespace std;
int n,tot;
double x[N],y[N],z[N],dis[N];
bool vis[N];
double mul(double x) {return x*x;}
double dist(int a,int b)
{
return sqrt(mul(x[a]-x[b])+mul(y[a]-y[b]));
}
bool check(double mid)
{
memset(vis,,sizeof(vis));
for (int i=;i<=n;i++) dis[i]=fabs(z[]-z[i])-mid*dist(,i);
vis[]=;
int tot=n-;
int id=-;
double val=0.0,tmp=0.0;
while(tot--)
{
id=-;
for (int i=;i<=n;i++)
{
if(!vis[i])
{
if(id==-) id=i;
else if(dis[id]>dis[i]) id=i;
}
}
tmp+=dis[id];
vis[id]=;
for (int i=;i<=n;i++)
{
if(!vis[i])
{
dis[i]=min(dis[i],fabs(z[i]-z[id])-mid*dist(i,id));
}
}
}
return tmp<=0.0;
}
int main()
{
while (scanf("%d",&n)!=EOF)
{
if (!n) break;
for (int i=;i<=n;i++) scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
double l=0.0,r=0.0,mid;
for (int i=;i<=n;i++)
r+=fabs(z[i]-z[]);
for(int i=;i<=;i++)
{
mid=(l+r)/2.0;
if (check(mid)) r=mid;
else l=mid; }
printf("%.3lf\n",r);
}
return ;
}

最新文章

  1. 通过iTop Webservice接口丰富OQL的功能
  2. jquery.cookie() 的使用(原)
  3. WebService基本概念及原理
  4. python 类中staticmethod,classmethod,普通方法
  5. android_audio
  6. C#根据CPU+磁盘标号来注册软件
  7. autotool相关:AC_ARG_ENABLE的用法
  8. 2014ACM/ICPC亚洲区西安站 复旦命题
  9. asp.net获取select值的方法
  10. Umbraco Forms 使Rendering Forms scripts 在不同的template中
  11. ios开发——实战OC篇&amp;SQLite3的实际应用
  12. idHTTP最简洁的修改和取得Cookie例子
  13. 如何让HTML的编写更具结构性
  14. (19)IO流之字符流FileReader和FileWriter,缓冲字符流---缓冲输入字符流BufferedReader和缓冲输出字符流BufferedWriter
  15. vue 部署404
  16. C++ 之sizeof运算符
  17. Leetcode 125.验证回文串 By Python
  18. linux 网卡配置信息
  19. MVC4.0 IIS 7.5 详细错误 - 404.0 - Not Found
  20. GO里的“指针”

热门文章

  1. leetcode笔记10 Intersection of Two Arrays(求交集)
  2. SQL注入篇二------利用burp盲注,post注入,http头注入,利用burpsuit找注入点,宽字节注入
  3. .net 使用com组件操作word遇到的一些问题
  4. [JSON].getObj( keyPath )
  5. MD5接口解密操作_接口签名校验
  6. ionic ios样式偏移解决方案。
  7. Java进阶知识点:并发容器背后的设计理念
  8. 线性代数之——A 的 LU 分解
  9. 常用算法Java实现之冒泡排序
  10. lintcode-143-排颜色 II