POJ 2728 最优比率生成树
生成 poj 最优
2023-09-11 14:13:59 时间
题意:
让你求一颗最小比率生成树。
思路:
我总结过了,在这里:http://blog.csdn.net/u013761036/article/details/26666261
让你求一颗最小比率生成树。
思路:
我总结过了,在这里:http://blog.csdn.net/u013761036/article/details/26666261
提示几个地方,这个题目的最小树记得用普利姆,别用克鲁斯卡尔,克鲁斯卡尔会超时,在sort那个地方超时。别的没啥。
#include<stdio.h>
#include<math.h>
#define INF 1000000000
#define eps 0.0001
typedef struct
{
double x ,y ,z;
}NODE;
NODE node[1100];
int mark[1100];
double d[1100];
double diss(NODE a ,NODE b)
{
double tmp = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
return sqrt(tmp);
}
double abss(double x)
{
return x > 0 ? x : -x;
}
double Prim(int n ,double L)
{
double ans = 0;
for(int i = 2 ;i <= n ;i ++)
{
double dis = diss(node[1] ,node[i]);
//d[i] = dis - L * abss(node[1].z - node[i].z);
d[i] = abss(node[1].z - node[i].z) - L * dis;
mark[i] = 0;
}
mark[1] = 1;
for(int ii = 1 ;ii < n ;ii ++)
{
double Min = INF;
int mk = -1;
for(int i = 1 ;i <= n ;i ++)
{
if(!mark[i] && d[i] < Min)
{
mk = i;
Min = d[i];
}
}
if(mk == -1) return ans;
ans += Min;
mark[mk] = 1;
for(int i = 1 ;i <= n ;i ++)
{
if(mark[i]) continue;
double dis = diss(node[mk] ,node[i]);
//double tmp = dis - L * abss(node[mk].z - node[i].z);
double tmp = abss(node[mk].z - node[i].z) - dis * L;
if(d[i] > tmp) d[i] = tmp;
}
}
return ans;
}
int main ()
{
int n ,m ,i ,j;
while(~scanf("%d" ,&n) && n)
{
for(i = 1 ;i <= n ;i ++)
scanf("%lf %lf %lf" ,&node[i].x ,&node[i].y ,&node[i].z);
double low ,up ,mid ,ans = 0;
low = 0 ,up = INF;
while(up - low >= eps)
{
mid = (low + up) / 2;
double tmp = Prim(n ,mid);
if(tmp >= 0)
ans = low = mid;
else up = mid;
}
printf("%.3f\n" ,ans);
}
return 0;
}
相关文章
- H5+JS生成验证码
- mysql 编号生成
- hibernate正向生成数据库表以及配置——TestStu.java
- hibernate正向生成数据库表以及配置——Student.java
- Solidworks如何生成爆炸图
- 使用PHP类库PHPqrCode生成二维码
- C# 二维码生成
- Sql Server生成测试数据
- 【项目实战】spring-boot-configuration-processor 一个用于生成配置元数据的注解处理器
- 【生成有序序列】借鉴雪花算法实现的一种长度更短的有序序列生成算法
- ZOJ 1542 POJ 1861 Network 网络 最小生成树,求最长边,Kruskal算法
- Linux 下shell命令生成随机字符串——筑梦之路
- HDU 1863 畅通project (最小生成树是否存在)
- 【数据挖掘】十大算法之ID3决策树生成算法和CART分类回归树算法
- 安装git后生成ssh公钥方法
- 【AIGC】4、DDPM 简介 | 使用随机噪声来生成图像
- mysql 生成雪花ID sql 亲自验证通过
- 【语言模型生成分子更好】Language models can learn complex molecular distributions
- 【DL】第 7 章 :用于音乐生成的Transformers和 MuseGAN