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使用Javassist动态生成HelloWorld类

《Java使用Javassist动态生成HelloWorld类》Javassist是一个非常强大的字节码操作和定义库,它允许开发者在运行时创建新的类或者修改现有的类,本文将简单介绍如何使用Javass... 目录1. Javassist简介2. 环境准备3. 动态生成HelloWorld类3.1 创建CtC

Python从Word文档中提取图片并生成PPT的操作代码

《Python从Word文档中提取图片并生成PPT的操作代码》在日常办公场景中,我们经常需要从Word文档中提取图片,并将这些图片整理到PowerPoint幻灯片中,手动完成这一任务既耗时又容易出错,... 目录引言背景与需求解决方案概述代码解析代码核心逻辑说明总结引言在日常办公场景中,我们经常需要从 W

C#使用Spire.XLS快速生成多表格Excel文件

《C#使用Spire.XLS快速生成多表格Excel文件》在日常开发中,我们经常需要将业务数据导出为结构清晰的Excel文件,本文将手把手教你使用Spire.XLS这个强大的.NET组件,只需几行C#... 目录一、Spire.XLS核心优势清单1.1 性能碾压:从3秒到0.5秒的质变1.2 批量操作的优雅

Python使用python-pptx自动化操作和生成PPT

《Python使用python-pptx自动化操作和生成PPT》这篇文章主要为大家详细介绍了如何使用python-pptx库实现PPT自动化,并提供实用的代码示例和应用场景,感兴趣的小伙伴可以跟随小编... 目录使用python-pptx操作PPT文档安装python-pptx基础概念创建新的PPT文档查看

在ASP.NET项目中如何使用C#生成二维码

《在ASP.NET项目中如何使用C#生成二维码》二维码(QRCode)已广泛应用于网址分享,支付链接等场景,本文将以ASP.NET为示例,演示如何实现输入文本/URL,生成二维码,在线显示与下载的完整... 目录创建前端页面(Index.cshtml)后端二维码生成逻辑(Index.cshtml.cs)总结

Python实现数据可视化图表生成(适合新手入门)

《Python实现数据可视化图表生成(适合新手入门)》在数据科学和数据分析的新时代,高效、直观的数据可视化工具显得尤为重要,下面:本文主要介绍Python实现数据可视化图表生成的相关资料,文中通过... 目录前言为什么需要数据可视化准备工作基本图表绘制折线图柱状图散点图使用Seaborn创建高级图表箱线图热

SQLServer中生成雪花ID(Snowflake ID)的实现方法

《SQLServer中生成雪花ID(SnowflakeID)的实现方法》:本文主要介绍在SQLServer中生成雪花ID(SnowflakeID)的实现方法,文中通过示例代码介绍的非常详细,... 目录前言认识雪花ID雪花ID的核心特点雪花ID的结构(64位)雪花ID的优势雪花ID的局限性雪花ID的应用场景

Django HTTPResponse响应体中返回openpyxl生成的文件过程

《DjangoHTTPResponse响应体中返回openpyxl生成的文件过程》Django返回文件流时需通过Content-Disposition头指定编码后的文件名,使用openpyxl的sa... 目录Django返回文件流时使用指定文件名Django HTTPResponse响应体中返回openp

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

Java设计模式---迭代器模式(Iterator)解读

《Java设计模式---迭代器模式(Iterator)解读》:本文主要介绍Java设计模式---迭代器模式(Iterator),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录1、迭代器(Iterator)1.1、结构1.2、常用方法1.3、本质1、解耦集合与遍历逻辑2、统一