题目链接: id=3621">http://poj.org/problem?id=3621
在一个有向图中选一个环,使得环上的点权和除以边权和最大。求这个比值。
经典的分数规划问题,我认为这两篇题解写得非常清楚,能够參考一下http://blog.csdn.net/gengmingrui/article/details/47443705,http://blog.csdn.net/wall_f/article/details/8221807
个人认为01分数规划差点儿都是二分或者迭代比值,从而找到一个最优解,使得原来的函数值等于0
#include<cstdio>
#include<cstring>
#include<queue>
#define eps 1e-3
#define MAXN 1010
using namespace std;
struct T
{
int v;
int w;
int next;
}edge[5005];
int cnt,head[MAXN];
void add_edge(int u,int v,int w)
{
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
int n,m;
int w[MAXN];
double dis[MAXN];
bool inque[MAXN];
int vis[MAXN];
bool SPFA(double R)//SPFA推断负权环
{
queue<int> myque;
memset(inque,0,sizeof inque);
memset(vis,0,sizeof vis);
for(int i = 1; i <= n; i++)
dis[i] = 1e15;
myque.push(1);
dis[1] = 0;
inque[1] = 1;
vis[1]++;
while(!myque.empty())
{
int u = myque.front();
myque.pop();
inque[u] = 0;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
int y = edge[i].w;
if(dis[u] + R*y - w[u] < dis[v])
{
dis[v] = dis[u] + R*y - w[u];
if(!inque[v])
{
myque.push(v);
inque[v] = 1;
vis[v]++;
if(vis[v] > n) return 1;
}
}
}
}
return 0;
}
int main()
{
memset(head,-1,sizeof head);
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)
scanf("%d",&w[i]);
for(int i = 1; i <= m; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c);
}
double l = 0,r = 10000,mid;
while(r - l > eps)
{
mid = (l+r)/2;
if(SPFA(mid)) l = mid;//因为我们是把权值取反了的。因此题解中的R过大变成了R过小
else r = mid;
}
printf("%.2lf\n",l);
return 0;
}
POJ3621 Sightseeing Cows(最优比率环)的更多相关文章
-
POJ3621 Sightseeing Cows 最优比率环 二分法
题目链接:http://poj.org/problem?id=3621 Sightseeing Cows Time Limit: 1000MS Memory Limit: 65536K Total ...
-
POJ 3621 Sightseeing Cows [最优比率环]
感觉去年9月的自己好$naive$ http://www.cnblogs.com/candy99/p/5868948.html 现在不也是嘛 裸题,具体看学习笔记 二分答案之后判负环就行了 $dfs$ ...
-
Sightseeing Cows(最优比率环)
Sightseeing Cows Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8915 Accepted: 3000 ...
-
【poj3621】最优比率环
题意: 给定n个点,每个点有一个开心度F[i],每个点有m条单向边,每条边有一个长度d,要求一个环,使得它的 开心度的和/长度和 这个比值最大.n<=1000,m<=5000 题解: 最优 ...
-
[转]01分数规划算法 ACM 二分 Dinkelbach 最优比率生成树 最优比率环
01分数规划 前置技能 二分思想最短路算法一些数学脑细胞? 问题模型1 基本01分数规划问题 给定nn个二元组(valuei,costi)(valuei,costi),valueivaluei是选择此 ...
-
poj 3621(最优比率环)
题目链接:http://poj.org/problem?id=3621 思路:之前做过最小比率生成树,也是属于0/1整数划分问题,这次碰到这道最优比率环,很是熟悉,可惜精度没控制好,要不就是wa,要不 ...
-
POJ 3621-Sightseeing Cows-最优比率环|SPFA+二分
最优比率环问题.二分答案,对于每一个mid,把节点的happy值归类到边上. 对于每条边,用mid×weight减去happy值,如果不存在负环,说明还可以更大. /*---------------- ...
-
POJ 3621 Sightseeing Cows (最优比率环 01分数划分)
题意: 给定L个点, P条边的有向图, 每个点有一个价值, 但只在第一经过获得, 每条边有一个花费, 每次经过都要付出这个花费, 在图中找出一个环, 使得价值之和/花费之和 最大 分析: 这道题其实并 ...
-
POJ 3621:Sightseeing Cows(最优比率环)
http://poj.org/problem?id=3621 题意:有n个点m条有向边,每个点有一个点权val[i],边有边权w(i, j).找一个环使得Σ(val) / Σ(w)最大,并输出. 思路 ...
随机推荐
-
spark发行版笔记9
感谢DT大数据梦工厂支持提供技术支持,DT大数据梦工厂专注于Spark发行版定制. 本期概览: 1 Receiver生命全周期 首先,我们找到数据来源的入口,入口如下 Receiver的设计是极其巧妙 ...
-
javascript中call函数与apply
javascript中的call方法使当前对象可以调用另一个对象的方法,即改变this的指向内容 var first_object = { num: 42 }; var second_object = ...
-
Java并发包中Semaphore的工作原理、源码分析及使用示例
1. 信号量Semaphore的介绍 我们以一个停车场运作为例来说明信号量的作用.假设停车场只有三个车位,一开始三个车位都是空的.这时如果同时来了三辆车,看门人允许其中它们进入进入,然后放下车拦.以后 ...
-
初学者的checklist:对于QTP,你应该知道的9个基本概念
学习QTP或者其他相关任何工具的方法都是首先把基本的概念过一遍.正所谓砍柴不怕磨刀功,一旦你对这些概念熟悉了,你就可以学习该工具的高级部分了.写这篇文章的目标是列出初学QTP的人应该掌握的所有基本概念 ...
-
C语言面试题分类->;字符串处理
1.strlen:计算字符串长度(不包含'\0') 实现想法:遍历字符串,直到'\0'结束 #include<stdio.h> #include<stdlib.h> #incl ...
-
shell脚本学习-分支结构
跟着RUNOOB网站的教程学习的笔记 if语法格式 if condition then command1 command2 ... commandN fi 写成一行(使用于终端命令提示符): ]; t ...
-
P2750 贰五语言Two Five USACO5.5 记忆化搜索
正解:记搜+逼近 解题报告: 神仙题预警,,, 我真滴觉得还是挺难的了,,, 大概说下思路趴QAQ 首先我们要知道逼近法是什么! 逼近法,有点像二分的思路,以这题为例举个eg 假如它给了个数字k.我们 ...
-
python 异步IO( asyncio) 协程
python asyncio 网络模型有很多中,为了实现高并发也有很多方案,多线程,多进程.无论多线程和多进程,IO的调度更多取决于系统,而协程的方式,调度来自用户,用户可以在函数中yield一个状态 ...
-
【实践总结】给Centos和Ubuntu设置静态网络IP以及配置ssh功能
作为一名以Windows平台为主的开发者,在接触和使用Linux系统的过程中总会遇到一系列的问题.每当这时候,我相信大部分人是和我一样的处理办法,就是网上各种搜索尝试直到问题解决为止,而有些问题,前后 ...
-
基于windows的Redis后台服务安装卸载管理
首先,需要你进入你的Redis解压根目录,例如,类似于我下图的这样子: 接着打开你的cmd,使用cd命令切换到该目录,或者直接在上图的地址栏输入“cmd”并回车.这里为什么让你先使用资源管理器找到你的 ...