热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

01分数规划——最有比率环pku3621SightseeingCows

http:poj.orgproblem?id3621题意:给定一张图,边上有花费,点上有收益,点可以多次经过,

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

题意:

给定一张图,边上有花费,点上有收益,点可以多次经过,但是收益不叠加,边也可以多次经过,但是费用叠加。求一个环使得收益和/花费和最大,输出这个比值。

思路:(转载)

 首先的一个结论就是,不会存在环套环的问题,即最优的方案一定是一个单独的环,而不是大环套着小环的形式。这个的证明其实非常的简单,大家可以自己想一下(提示,将大环上的收益和记为x1,花费为y1,小环上的为x2,y2。重叠部分的花费为S。表示出来分类讨论即可)。有了这个结论,我们就可以将花费和收益都转移到边上来了,因为答案最终一定是一个环,所以我们将每一条边的收益规定为其终点的收益,这样一个环上所有的花费和收益都能够被正确的统计。

解决了蛋疼的问题之后,就是01分数规划的部分了,我们只需要计算出D数组后找找有没有正权环即可,不过这样不太好,不是我们熟悉的问题,将D数组全部取反之后,问题转换为查找有没有负权环,用spfa或是bellman_ford都可以。这道题目就是典型的不适合用Dinkelbach,记录一个负权环还是比较麻烦的,所以二分搞定。

上面讲的挺清晰的。。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include #define CL(a,num) memset((a),(num),sizeof(a))
#define iabs(x) ((x) > 0 ? (x) : -(x))
#define Min(a,b) (a) > (b)? (b):(a)
#define Max(a,b) (a) > (b)? (a):(b)#define ll __int64
#define inf 0x7f7f7f7f
#define MOD 1073741824
#define lc l,m,rt<<1
#define rc m &#43; 1,r,rt<<1|1
#define pi acos(-1.0)
#define test puts("<------------------->")
#define maxn 100007
#define M 5007
#define N 1007
using namespace std;
//freopen("din.txt","r",stdin);const double eps &#61; 1e-6;struct node
{int u,v;double w;int next;
}g[M];
int head[N],ct;double val[N];
double dis[N];
bool vt[N];
int que[1000003],l,r;
int num[N];int n,m;int dblcmp(double x)
{if (x > eps) return 1;else if (x <-eps) return -1;else return 0;
}
void add(int u,int v,int w)
{g[ct].v &#61; v;g[ct].w &#61; w;g[ct].next &#61; head[u];head[u] &#61; ct&#43;&#43;;
}
int spfa(double mid)
{int i;l &#61; r &#61; 0;for (i &#61; 0; i dis[u] &#43; mid*g[j].w - val[i]){dis[i] &#61; dis[u] &#43; mid*g[j].w - val[i];if (!vt[i]){vt[i] &#61; true;que[&#43;&#43;r] &#61; i;if (&#43;&#43;num[i] > n) return 1;//进入队列的次数超过n次&#xff0c;表示存在负环}}}}return 0;
}
int main()
{int i;double z;int x,y;while (~scanf("%d%d",&n,&m)){CL(head,-1); ct &#61; 0;double l &#61; 0;double r &#61; 0;for (i &#61; 0; i }

  

 

转:https://www.cnblogs.com/E-star/archive/2013/01/21/2870298.html



推荐阅读
  • 在稀疏直接法视觉里程计中,通过优化特征点并采用基于光度误差最小化的灰度图像线性插值技术,提高了定位精度。该方法通过对空间点的非齐次和齐次表示进行处理,利用RGB-D传感器获取的3D坐标信息,在两帧图像之间实现精确匹配,有效减少了光度误差,提升了系统的鲁棒性和稳定性。 ... [详细]
  • 本文作为“实现简易版Spring系列”的第五篇,继前文深入探讨了Spring框架的核心技术之一——控制反转(IoC)之后,将重点转向另一个关键技术——面向切面编程(AOP)。对于使用Spring框架进行开发的开发者来说,AOP是一个不可或缺的概念。了解AOP的背景及其基本原理,对于掌握这一技术至关重要。本文将通过具体示例,详细解析AOP的实现机制,帮助读者更好地理解和应用这一技术。 ... [详细]
  • 本项目在Java Maven框架下,利用POI库实现了Excel数据的高效导入与导出功能。通过优化数据处理流程,提升了数据操作的性能和稳定性。项目已发布至GitHub,当前最新版本为0.0.5。该项目不仅适用于小型应用,也可扩展用于大型企业级系统,提供了灵活的数据管理解决方案。GitHub地址:https://github.com/83945105/holygrail,Maven坐标:`com.github.83945105:holygrail:0.0.5`。 ... [详细]
  • BZOJ1034 详细解析与算法优化
    本文深入解析了BZOJ1034问题,并提出了优化算法。通过借鉴广义田忌赛马的贪心策略,当己方当前最弱的马优于对方最弱的马时进行匹配;同样地,若己方当前最强的马优于对方最强的马,也进行匹配。此方法在保证胜率的同时,有效提升了算法效率。 ... [详细]
  • 如何在 Java LinkedHashMap 中高效地提取首个或末尾的键值对? ... [详细]
  • 本文详细介绍了如何在Linux系统中搭建51单片机的开发与编程环境,重点讲解了使用Makefile进行项目管理的方法。首先,文章指导读者安装SDCC(Small Device C Compiler),这是一个专为小型设备设计的C语言编译器,适合用于51单片机的开发。随后,通过具体的实例演示了如何配置Makefile文件,以实现代码的自动化编译与链接过程,从而提高开发效率。此外,还提供了常见问题的解决方案及优化建议,帮助开发者快速上手并解决实际开发中可能遇到的技术难题。 ... [详细]
  • 深入解析Gradle中的Project核心组件
    在Gradle构建系统中,`Project` 是一个核心组件,扮演着至关重要的角色。通过使用 `./gradlew projects` 命令,可以清晰地列出当前项目结构中包含的所有子项目,这有助于开发者更好地理解和管理复杂的多模块项目。此外,`Project` 对象还提供了丰富的配置选项和生命周期管理功能,使得构建过程更加灵活高效。 ... [详细]
  • 题目描述:小K不幸被LL邪教洗脑,洗脑程度之深使他决定彻底脱离这个邪教。在最终离开前,他计划再进行一次亚瑟王游戏。作为最后一战,他希望这次游戏能够尽善尽美。众所周知,亚瑟王游戏的结果很大程度上取决于运气,但通过合理的策略和算法优化,可以提高获胜的概率。本文将详细解析洛谷P3239 [HNOI2015] 亚瑟王问题,并提供具体的算法实现方法,帮助读者更好地理解和应用相关技术。 ... [详细]
  • Java 9 中 SafeVarargs 注释的使用与示例解析 ... [详细]
  • 2019年后蚂蚁集团与拼多多面试经验详述与深度剖析
    2019年后蚂蚁集团与拼多多面试经验详述与深度剖析 ... [详细]
  • Spring框架入门指南:专为新手打造的详细学习笔记
    Spring框架是Java Web开发中广泛应用的轻量级应用框架,以其卓越的功能和出色的性能赢得了广大开发者的青睐。本文为初学者提供了详尽的学习指南,涵盖基础概念、核心组件及实际应用案例,帮助新手快速掌握Spring框架的核心技术与实践技巧。 ... [详细]
  • MySQL性能优化与调参指南【数据库管理】
    本文详细探讨了MySQL数据库的性能优化与参数调整技巧,旨在帮助数据库管理员和开发人员提升系统的运行效率。内容涵盖索引优化、查询优化、配置参数调整等方面,结合实际案例进行深入分析,提供实用的操作建议。此外,还介绍了常见的性能监控工具和方法,助力读者全面掌握MySQL性能优化的核心技能。 ... [详细]
  • 如何在 Python 编程中实现各种数据类型的字符串转换? ... [详细]
  • 在将 MySQL 查询转换为 LINQ 时遇到了挑战,特别是在使用 Any 方法时。尽管已成功建立了连接并执行了查询,但返回的结果集中 lambda 表达式部分为空,导致无法正确映射数据。本文探讨了这一问题的根源,并提供了几种可能的解决方案,包括调整查询逻辑和优化 LINQ 表达式的建议。 ... [详细]
  • MongoDB Aggregates.group() 方法详解与编程实例 ... [详细]
author-avatar
hja2045905
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有