感觉去年9月的自己好$naive$ http://www.cnblogs.com/candy99/p/5868948.html
现在不也是嘛
裸题,具体看学习笔记
二分答案之后判负环就行了
$dfs$版超快
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int N=,M=;
const double eps=1e-;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,u,v;
double f[N];
struct edge{
int v,ne;
double w;
}e[M<<];
int h[N],cnt=;
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
}
double d[N];
int inq[N],num[N];
int q[N],head,tail;
inline void lop(int &x){if(x==N) x=;}
bool NegativeCircle(double mid){
head=tail=;
for(int i=;i<=n;i++) d[i]=,inq[i]=,q[tail++]=i,num[i]=;
while(head!=tail){
int u=q[head++];lop(head);inq[u]=;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;double w=mid*e[i].w-f[u];
if(d[v]>d[u]+w){
d[v]=d[u]+w;
if(!inq[v]){
inq[v]=;q[tail++]=v;lop(tail);
if(++num[v]>n) return true;
}
}
}
}
return false;
}
inline bool check(double mid){return NegativeCircle(mid);}
void solve(){
double l=,r=;
while(r-l>eps){
double mid=(l+r)/2.0;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.2f",l);
}
int main(){
freopen("in","r",stdin);
n=read();m=read();
for(int i=;i<=n;i++) f[i]=read();
for(int i=;i<=m;i++) u=read(),v=read(),ins(u,v,read());
solve();
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int N=,M=;
const double eps=1e-;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,u,v;
double f[N];
struct edge{
int v,ne;
double w;
}e[M<<];
int h[N],cnt=;
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
}
double d[N];
int vis[N],cl;
bool dfs(int u,double mid){
vis[u]=cl;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;double w=mid*e[i].w-f[u];
if(d[v]>d[u]+w){
d[v]=d[u]+w;
if(vis[v]==vis[u]) return true;
else if(dfs(v,mid)) return true;
}
}
vis[u]=;
return false;
}
bool NegativeCircle(double mid){
memset(vis,,sizeof(vis));
for(cl=;cl<=n;cl++) if(dfs(cl,mid)) return true;
return false;
}
inline bool check(double mid){return NegativeCircle(mid);}
void solve(){
double l=,r=;
while(r-l>eps){
double mid=(l+r)/2.0;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.2f",l);
}
int main(){
freopen("in","r",stdin);
n=read();m=read();
for(int i=;i<=n;i++) f[i]=read();
for(int i=;i<=m;i++) u=read(),v=read(),ins(u,v,read());
solve();
}
POJ 3621 Sightseeing Cows [最优比率环]的更多相关文章
-
POJ3621 Sightseeing Cows 最优比率环 二分法
题目链接:http://poj.org/problem?id=3621 Sightseeing Cows Time Limit: 1000MS Memory Limit: 65536K Total ...
-
POJ3621 Sightseeing Cows(最优比率环)
题目链接:id=3621">http://poj.org/problem?id=3621 在一个有向图中选一个环,使得环上的点权和除以边权和最大.求这个比值. 经典的分数规划问题,我认 ...
-
POJ 3621 Sightseeing Cows 【01分数规划+spfa判正环】
题目链接:http://poj.org/problem?id=3621 Sightseeing Cows Time Limit: 1000MS Memory Limit: 65536K Total ...
-
[POJ 3621] Sightseeing Cows
[题目链接] http://poj.org/problem?id=3621 [算法] 01分数规划(最优比率环) [代码] #include <algorithm> #include &l ...
-
POJ 3621 Sightseeing Cows (最优比率环 01分数划分)
题意: 给定L个点, P条边的有向图, 每个点有一个价值, 但只在第一经过获得, 每条边有一个花费, 每次经过都要付出这个花费, 在图中找出一个环, 使得价值之和/花费之和 最大 分析: 这道题其实并 ...
-
POJ 3621 Sightseeing Cows(最优比例环+SPFA检测)
Sightseeing Cows Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10306 Accepted: 3519 ...
-
POJ 3621 Sightseeing Cows 01分数规划,最优比例环的问题
http://www.cnblogs.com/wally/p/3228171.html 题解请戳上面 然后对于01规划的总结 1:对于一个表,求最优比例 这种就是每个点位有benefit和cost,这 ...
-
POJ 3621 Sightseeing Cows | 01分数规划
题目: http://poj.org/problem?id=3621 题解: 二分答案,检查有没有负环 #include<cstdio> #include<algorithm> ...
-
POJ 3621 Sightseeing Cows (bellman-Ford + 01分数规划)
题意:给出 n 个点 m 条有向边,要求选出一个环,使得这上面 点权和/边权和 最大. 析:同样转成是01分数规划的形式,F / L 要这个值最大,也就是 G(r) = F - L * r 这个值为0 ...
随机推荐
-
前端之css、JavaScript和DOM
css position 一般组合 relative+absolute,以relative为父元素,absolute依照relative进行定位. opcity: 0.5 透明度 z-index: 层 ...
-
失恋28天-缝补礼物(codevs 2503)
2503 失恋28天-缝补礼物 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold 题解 查看运行结果 题目描述 Description 话说上回他给女孩送 ...
-
Java工程转换为Maven工程-b
1. 前言 在开发中经常要建立一个Maven的子工程,对于没有模板的同学来说从Java工程来转换也是一个不错的选择.本文就如何从一个Java工程创建一个Maven工程做了一个介绍,相信对于将一个Jav ...
-
uva 1422 - Processor(二分+优先队列)
题目链接:uva 1422 - Processor 题目大意:有一个机器要处理一些问题,给出这些问题可以开始的时间和必须完成的时间,以及任务的工作量,问说机器必须以最少每秒多少得工作量才能完成这些任务 ...
-
data-theme 几种值的样式
代码片段: <div data-role="page"> <div data-role="header"> <h1>The ...
-
struts2 taglib struts标签学习整理中
项目中经常会用到struts标签,这样可以减少代码量. select用法: <s:select list="#request.sysTypes" name="rul ...
-
Jsp分页实例---真分页
网页的分页功能的实现比较简单,实现方法也多种多样. 今天总结一个简单的Jsp真分页实例. 首先,提到分页就要先明确一个概念,何为真分页何谓假分页. 假分页:一次性从数据库读出表的所有数据一次性的返回给 ...
-
在VMware上安装ubuntu,并且SecureCRT远程连接
工具: VMware:VMware-workstation-full_12.5.5.17738.exe Ubuntu镜像:ubuntu-16.04-server-amd64.iso 远程连接工具-- ...
-
Django1-10-5管理界面中文设置
先确定一下版本是否更高,低版本设置(settings.py文件): LANGUAGE_CODE = 'zh-CN'TIME_ZONE = 'Asia/Shanghai' 但是新版本就会提示不识别zh- ...
-
遍历二叉树 traversing binary tree 线索二叉树 threaded binary tree 线索链表 线索化
遍历二叉树 traversing binary tree 线索二叉树 threaded binary tree 线索链表 线索化 1. 二叉树3个基本单元组成:根节点.左子树.右子树 以L.D.R ...