POJ 3621 Sightseeing Cows [最优比率环]

时间:2022-05-24 02:23:20

感觉去年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 [最优比率环]的更多相关文章

  1. POJ3621 Sightseeing Cows 最优比率环 二分法

    题目链接:http://poj.org/problem?id=3621 Sightseeing Cows Time Limit: 1000MS   Memory Limit: 65536K Total ...

  2. POJ3621 Sightseeing Cows&lpar;最优比率环&rpar;

    题目链接:id=3621">http://poj.org/problem?id=3621 在一个有向图中选一个环,使得环上的点权和除以边权和最大.求这个比值. 经典的分数规划问题,我认 ...

  3. POJ 3621 Sightseeing Cows 【01分数规划&plus;spfa判正环】

    题目链接:http://poj.org/problem?id=3621 Sightseeing Cows Time Limit: 1000MS   Memory Limit: 65536K Total ...

  4. &lbrack;POJ 3621&rsqb; Sightseeing Cows

    [题目链接] http://poj.org/problem?id=3621 [算法] 01分数规划(最优比率环) [代码] #include <algorithm> #include &l ...

  5. POJ 3621 Sightseeing Cows (最优比率环 01分数划分)

    题意: 给定L个点, P条边的有向图, 每个点有一个价值, 但只在第一经过获得, 每条边有一个花费, 每次经过都要付出这个花费, 在图中找出一个环, 使得价值之和/花费之和 最大 分析: 这道题其实并 ...

  6. POJ 3621 Sightseeing Cows(最优比例环&plus;SPFA检测)

    Sightseeing Cows Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 10306   Accepted: 3519 ...

  7. POJ 3621 Sightseeing Cows 01分数规划,最优比例环的问题

    http://www.cnblogs.com/wally/p/3228171.html 题解请戳上面 然后对于01规划的总结 1:对于一个表,求最优比例 这种就是每个点位有benefit和cost,这 ...

  8. POJ 3621 Sightseeing Cows &vert; 01分数规划

    题目: http://poj.org/problem?id=3621 题解: 二分答案,检查有没有负环 #include<cstdio> #include<algorithm> ...

  9. POJ 3621 Sightseeing Cows &lpar;bellman-Ford &plus; 01分数规划&rpar;

    题意:给出 n 个点 m 条有向边,要求选出一个环,使得这上面 点权和/边权和 最大. 析:同样转成是01分数规划的形式,F / L 要这个值最大,也就是 G(r) = F - L * r 这个值为0 ...

随机推荐

  1. 前端之css、JavaScript和DOM

    css position 一般组合 relative+absolute,以relative为父元素,absolute依照relative进行定位. opcity: 0.5 透明度 z-index: 层 ...

  2. 失恋28天-缝补礼物&lpar;codevs 2503&rpar;

    2503 失恋28天-缝补礼物  时间限制: 1 s  空间限制: 32000 KB  题目等级 : 黄金 Gold 题解  查看运行结果     题目描述 Description 话说上回他给女孩送 ...

  3. Java工程转换为Maven工程-b

    1. 前言 在开发中经常要建立一个Maven的子工程,对于没有模板的同学来说从Java工程来转换也是一个不错的选择.本文就如何从一个Java工程创建一个Maven工程做了一个介绍,相信对于将一个Jav ...

  4. uva 1422 - Processor&lpar;二分&plus;优先队列)

    题目链接:uva 1422 - Processor 题目大意:有一个机器要处理一些问题,给出这些问题可以开始的时间和必须完成的时间,以及任务的工作量,问说机器必须以最少每秒多少得工作量才能完成这些任务 ...

  5. data-theme 几种值的样式

    代码片段: <div data-role="page"> <div data-role="header"> <h1>The ...

  6. struts2 taglib struts标签学习整理中

    项目中经常会用到struts标签,这样可以减少代码量. select用法: <s:select list="#request.sysTypes" name="rul ...

  7. Jsp分页实例---真分页

    网页的分页功能的实现比较简单,实现方法也多种多样. 今天总结一个简单的Jsp真分页实例. 首先,提到分页就要先明确一个概念,何为真分页何谓假分页. 假分页:一次性从数据库读出表的所有数据一次性的返回给 ...

  8. 在VMware上安装ubuntu&comma;并且SecureCRT远程连接

     工具: VMware:VMware-workstation-full_12.5.5.17738.exe Ubuntu镜像:ubuntu-16.04-server-amd64.iso 远程连接工具-- ...

  9. Django1-10-5管理界面中文设置

    先确定一下版本是否更高,低版本设置(settings.py文件): LANGUAGE_CODE = 'zh-CN'TIME_ZONE = 'Asia/Shanghai' 但是新版本就会提示不识别zh- ...

  10. 遍历二叉树 traversing binary tree 线索二叉树 threaded binary tree 线索链表 线索化

    遍历二叉树   traversing binary tree 线索二叉树 threaded binary tree 线索链表 线索化 1. 二叉树3个基本单元组成:根节点.左子树.右子树 以L.D.R ...