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

作者：hja2045905 | 来源：互联网 | 2023-10-10 19:01

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

http://poj.org/problem?id&＃61;3621

题意&＃xff1a;

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

思路&＃xff1a;&＃xff08;转载&＃xff09;

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

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

上面讲的挺清晰的。。

#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

推荐阅读

case
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
python
微软头条实习生分享深度学习自学指南

本文介绍了一位微软头条实习生自学深度学习的经验分享，包括学习资源推荐、重要基础知识的学习要点等。作者强调了学好Python和数学基础的重要性，并提供了一些建议。 ... [详细]

蜡笔小新 2023-12-14 20:58:32
case
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
case
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
python
向QTextEdit拖放文件的方法及实现步骤

本文介绍了在使用QTextEdit时如何实现拖放文件的功能，包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数，并结合QMimeData和QUrl等类，可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]

蜡笔小新 2023-12-14 16:06:38
get
实现下拉列表，点击其他位置自动隐藏效果的三种方式比较

目录实现效果：实现环境实现方法一：基本思路主要代码JavaScript代码总结方法二主要代码总结方法三基本思路主要代码JavaScriptHTML总结实 ... [详细]

蜡笔小新 2023-12-14 15:03:14
get
android listview OnItemClickListener失效原因

最近在做listview时发现OnItemClickListener失效的问题，经过查找发现是因为button的原因。不仅listitem中存在button会影响OnItemClickListener事件的失效，还会导致单击后listview每个item的背景改变，使得item中的所有有关焦点的事件都失效。本文给出了一个范例来说明这种情况，并提供了解决方法。 ... [详细]

蜡笔小新 2023-12-14 14:25:50
default
关于cuowu类的错误提示和使用AdjustmentListener的问题

本文讨论了一个关于cuowu类的问题，作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案，并给出了两个可能导致错误的原因。 ... [详细]

蜡笔小新 2023-12-13 22:09:56
process
Linux进程控制块PCBtask_struct结构体结构及作用详解

本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用，包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]

蜡笔小新 2023-12-13 21:31:18
process
推荐系统遇上深度学习(十七）详解推荐系统中的常用评测指标

原创：石晓文小小挖掘机2018-06-18笔者是一个痴迷于挖掘数据中的价值的学习人，希望在平日的工作学习中，挖掘数据的价值， ... [详细]

蜡笔小新 2023-12-13 19:35:25
process
使用多进程实现TCP服务端的优势和注意事项

本文介绍了为什么要使用多进程处理TCP服务端，多进程的好处包括可靠性高和处理大量数据时速度快。然而，多进程不能共享进程空间，因此有一些变量不能共享。文章还提供了使用多进程实现TCP服务端的代码，并对代码进行了详细注释。 ... [详细]

蜡笔小新 2023-12-13 18:25:30
get
[CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]

蜡笔小新 2023-12-13 09:08:55
get
Go GUIlxn/walk 学习3.菜单栏和工具栏的具体实现

本文介绍了使用Go语言的GUI库lxn/walk实现菜单栏和工具栏的具体方法，包括消息窗口的产生、文件放置动作响应和提示框的应用。部分代码来自上一篇博客和lxn/walk官方示例。文章提供了学习GUI开发的实际案例和代码示例。 ... [详细]

蜡笔小新 2023-12-12 20:56:55
copy
clone的fork与pthread_create创建线程有何不同

本文讨论了clone的fork与pthread_create创建线程的不同之处。进程是一个指令执行流及其执行环境，其执行环境是一个系统资源的集合。在调用系统调用fork创建一个进程时，子进程只是完全复制父进程的资源，这样得到的子进程独立于父进程，具有良好的并发性。但是二者之间的通讯需要通过专门的通讯机制，另外通过fork创建子进程系统开销很大。因此，在某些情况下，使用clone或pthread_create创建线程可能更加高效。 ... [详细]

蜡笔小新 2023-12-12 20:00:06
copy
Go语言实现堆排序的详细教程

本文主要介绍了Go语言实现堆排序的详细教程，包括大根堆的定义和完全二叉树的概念。通过图解和算法描述，详细介绍了堆排序的实现过程。堆排序是一种效率很高的排序算法，时间复杂度为O(nlgn)。阅读本文大约需要15分钟。 ... [详细]

蜡笔小新 2023-12-12 16:23:00

hja2045905

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章