POJ 2728 Desert King (最小比率生成树,二分/迭代)

2024-04-23 20:08

本文主要是介绍POJ 2728 Desert King (最小比率生成树,二分/迭代),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:沙漠里的王国需要修建水渠,连接国都与村庄····。说白了求一棵树,每个点有三个坐标(x,y,z)。边的benifit为两点之间的距离,cost为两点的高度差。现在要求一棵树使得 cost / benift 最小。

题解:很显然任意两点之间都有边,所以是一个很稠密的图。用Prime。二分的话2800ms+, 迭代300ms+。

#include <cmath>
#include <iostream>
using namespace std;
#define MAX 1009
#define INF 99999999999
#define eps 1.0e-6  // 精度除以(0.001/2 )
struct NODE
{
int x, y, z;
} node[MAX];
double e[MAX][MAX];
double dis[MAX];
bool vis[MAX];
void build_map ( int n, double l )
{
for ( int i = 1; i <= n; i++ )
for ( int j = i + 1; j <= n; j++ )
{
double len = sqrt(0.0 + (node[i].x-node[j].x) 
* (node[i].x-node[j].x) + (node[i].y-node[j].y) * (node[i].y-node
[j].y));
double cost = fabs(0.0+node[i].z - node[j].z);
e[i][j] = e[j][i] = cost - l * len;
}
}
double prime ( int n )
{
int i, j, k;
double minc, ans = 0.0;
for ( i = 1; i <= n; i++ )
{
dis[i] = e[1][i];
vis[i] = false;
}
dis[1] = 0; vis[1] = true;
for ( i = 2; i <= n; i++ )
{
minc = INF; k = -1;
for ( j = 1; j <= n; j++ )
{
if ( !vis[j] && minc > dis[j] )
{
minc = dis[j];
k = j;
}
}
if ( minc == INF ) break;
ans += minc;
vis[k] = true;
for ( j = 1; j <= n; j++ )
if ( ! vis[j] && dis[j] > e[k][j] )
dis[j] = e[k][j];
}
return ans;
}
int main()
{
int n;
while ( scanf("%d",&n) && n )
{
for ( int i = 1; i <= n; i++ )
scanf("%d%d%d",&node[i].x, &node[i].y, &node
[i].z);
double mid, temp;
double high = 100, low = 0.0;
while ( 1 )
{
mid = ( high + low ) / 2;
build_map ( n, mid ) ;
temp = prime ( n );
if ( fabs(temp) <= eps ) break;
if ( temp < 0.0 )
high = mid - eps;
else
low = mid + eps;
}
printf("%.3lf\n",mid);
}
return 0;
}

 

迭代法:

#include <cmath>
#include <iostream>
using namespace std;
#define MAX 1001
#define INF 99999999999
#define eps 1.0e-6
struct NODE
{
int x, y, z;
} node[MAX];
double edge[MAX][MAX];
double len[MAX][MAX];
double cost[MAX][MAX];
double dis[MAX];
bool vis[MAX];
int pre[MAX];
void build_map ( int n, double l )
{
for ( int i = 1; i <= n; i++ )
for ( int j = i + 1; j <= n; j++ )
{
len[i][j] = len[j][i] = sqrt(0.0 + (node[i].x-node[j].x) * (node[i].x-node[j].x) + (node[i].y-node[j].y) * (node[i].y-node[j].y));
cost[i][j] = cost[j][i] = fabs ( 0.0 + node[i].z - node[j].z);
edge[i][j] = edge[j][i] = cost[i][j] - l * len[i][j];
}
}
double prime ( int n )  // 注意,与普通prime有区别
{
int i, j, k;
double minc, b = 0, c = 0;
for ( i = 1; i <= n; i++ )
{
dis[i] = edge[1][i];
pre[i] = 1;     // 所有点的前驱初始化为1
vis[i] = false;
}
dis[1] = 0;
vis[1] = true;
for ( i = 2; i <= n; i++ )
{
minc = INF; k = -1;
for ( j = 1; j <= n; j++ )
{
if ( ! vis[j] && minc > dis[j] )
{
minc = dis[j];
k = j;
}
}
if ( minc == INF ) break;
b += len[pre[k]][k];     //*********
c += cost[pre[k]][k];    //*********
vis[k] = true;
for ( j = 1; j <= n; j++ )
if ( ! vis[j] && dis[j] > edge[k][j] )
{
dis[j] = edge[k][j];
pre[j] = k;   //修改前驱
}
}
return c / b;
}
int main()
{
int n;
while ( scanf("%d",&n) && n )
{
for ( int i = 1; i <= n; i++ )
scanf("%d%d%d",&node[i].x, &node[i].y, &node[i].z);
double a = 0, b;
while ( 1 )
{
build_map ( n, a );
b = prime ( n );
if ( fabs(b-a) <= eps ) break;
a = b;
}
printf("%.3lf\n",b);
}
return 0;
}


 

这篇关于POJ 2728 Desert King (最小比率生成树,二分/迭代)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/929760

相关文章

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

Python如何自动生成环境依赖包requirements

《Python如何自动生成环境依赖包requirements》:本文主要介绍Python如何自动生成环境依赖包requirements问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录生成当前 python 环境 安装的所有依赖包1、命令2、常见问题只生成当前 项目 的所有依赖包1、

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

Java利用docx4j+Freemarker生成word文档

《Java利用docx4j+Freemarker生成word文档》这篇文章主要为大家详细介绍了Java如何利用docx4j+Freemarker生成word文档,文中的示例代码讲解详细,感兴趣的小伙伴... 目录技术方案maven依赖创建模板文件实现代码技术方案Java 1.8 + docx4j + Fr

C++变换迭代器使用方法小结

《C++变换迭代器使用方法小结》本文主要介绍了C++变换迭代器使用方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、源码2、代码解析代码解析:transform_iterator1. transform_iterat

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre