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

相关文章

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

Mybatis从3.4.0版本到3.5.7版本的迭代方法实现

《Mybatis从3.4.0版本到3.5.7版本的迭代方法实现》本文主要介绍了Mybatis从3.4.0版本到3.5.7版本的迭代方法实现,包括主要的功能增强、不兼容的更改和修复的错误,具有一定的参考... 目录一、3.4.01、主要的功能增强2、selectCursor example3、不兼容的更改二、

C/C++随机数生成的五种方法

《C/C++随机数生成的五种方法》C++作为一种古老的编程语言,其随机数生成的方法已经经历了多次的变革,早期的C++版本使用的是rand()函数和RAND_MAX常量,这种方法虽然简单,但并不总是提供... 目录C/C++ 随机数生成方法1. 使用 rand() 和 srand()2. 使用 <random

Flask 验证码自动生成的实现示例

《Flask验证码自动生成的实现示例》本文主要介绍了Flask验证码自动生成的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习... 目录生成图片以及结果处理验证码蓝图html页面展示想必验证码大家都有所了解,但是可以自己定义图片验证码

Python如何在Word中生成多种不同类型的图表

《Python如何在Word中生成多种不同类型的图表》Word文档中插入图表不仅能直观呈现数据,还能提升文档的可读性和专业性,本文将介绍如何使用Python在Word文档中创建和自定义各种图表,需要的... 目录在Word中创建柱形图在Word中创建条形图在Word中创建折线图在Word中创建饼图在Word

nginx生成自签名SSL证书配置HTTPS的实现

《nginx生成自签名SSL证书配置HTTPS的实现》本文主要介绍在Nginx中生成自签名SSL证书并配置HTTPS,包括安装Nginx、创建证书、配置证书以及测试访问,具有一定的参考价值,感兴趣的可... 目录一、安装nginx二、创建证书三、配置证书并验证四、测试一、安装nginxnginx必须有"-

Java实战之利用POI生成Excel图表

《Java实战之利用POI生成Excel图表》ApachePOI是Java生态中处理Office文档的核心工具,这篇文章主要为大家详细介绍了如何在Excel中创建折线图,柱状图,饼图等常见图表,需要的... 目录一、环境配置与依赖管理二、数据源准备与工作表构建三、图表生成核心步骤1. 折线图(Line Ch

浅析如何使用Swagger生成带权限控制的API文档

《浅析如何使用Swagger生成带权限控制的API文档》当涉及到权限控制时,如何生成既安全又详细的API文档就成了一个关键问题,所以这篇文章小编就来和大家好好聊聊如何用Swagger来生成带有... 目录准备工作配置 Swagger权限控制给 API 加上权限注解查看文档注意事项在咱们的开发工作里,API

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven