acwing-361. 观光奶牛(0/1分数规划)「建议收藏」

acwing-361. 观光奶牛(0/1分数规划)「建议收藏」给定一张 L 个点、P 条边的有向图,每个点都有一个权值 f[i],每条边都有一个权值 t[i]。求图中的一个环,使“环上各点的权值之和”除以“环上各边的权值之和”最大。输出这个最大值。注意:数据保证至少存在一个环。输入格式第一行包含两个整数 L 和 P。接下来 L 行每行一个整数,表示 f[i]。再接下来 P 行,每行三个整数 a,b,t[i],表示点 a 和 b 之间存在一条边,边的权值为 t[i]。输出格式输出一个数表示结果,保留两位小数。数据范围2≤L≤1000,2≤P≤50

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一张 L 个点、P 条边的有向图,每个点都有一个权值 f[i],每条边都有一个权值 t[i]。

求图中的一个环,使“环上各点的权值之和”除以“环上各边的权值之和”最大。

输出这个最大值。

注意:数据保证至少存在一个环。

输入格式
第一行包含两个整数 L 和 P。

接下来 L 行每行一个整数,表示 f[i]。

再接下来 P 行,每行三个整数 a,b,t[i],表示点 a 和 b 之间存在一条边,边的权值为 t[i]。

输出格式
输出一个数表示结果,保留两位小数。

数据范围
2≤L≤1000,
2≤P≤5000,
1≤f[i],t[i]≤1000

输入样例:
5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2
输出样例:
6.00

题解
0/1规划

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e3 + 10;
const int M = 5e4 + 10;
const double eps = 1e-6;
int value[N];
struct Edge{ 

int v,w,next;
}edge[M];
int head[N],c;
void add(int u,int v,int w){ 

edge[c].v = v;
edge[c].w = w;
edge[c].next = head[u];
head[u] = c ++;
}
int q[N],hh = 0,tt = 0;
int vis[N],cnt[N];
double dist[N];
bool check(double mid){ 

memset(vis,0,sizeof vis);
memset(cnt,0,sizeof cnt);
tt = hh = 0;
for(int i = 1;i <= n;i ++){ 

q[tt ++] = i;
vis[i] = true;
}
while(hh != tt){ 

int t = q[hh ++];
if(hh == N)hh = 0;
vis[t] = false;
for(int i = head[t];~i;i = edge[i].next){ 

int v = edge[i].v;
double w = value[t] - mid * edge[i].w;
if(dist[v] < dist[t] + w){ 

dist[v] = dist[t] + w;
cnt[v] = cnt[t] + 1;
if(cnt[v] >= n)return true;
if(!vis[v]){ 

vis[v] = true;
q[tt ++] = v;
if(tt == N)tt = 0;
}
}
}
}
return false;
}
int main(){ 

cin>>n>>m;
int x,y,w;
memset(head,-1,sizeof head);
for(int i = 1;i <= n;i ++)cin>>value[i];
for(int i = 0;i < m;i ++){ 

cin>>x>>y>>w;
add(x,y,w);
}
double l = 0.0,r = 1010;
while(r - l > 1e-4){ 

double mid = (l + r) / 2;
if(check(mid))l = mid;
else r = mid;
}
printf("%.2lf\n",l);
return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169113.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ssm框架过时了吗_spring实战

    ssm框架过时了吗_spring实战SpringSpring是一个开源的免费的框架Spring是一个轻量级的,非入侵式的框架控制反转(IOC),面向切面编程(AOP)支持事务的处理,对框架整合的支持IOC理论UserDaoUserDaoImpUserSeviceUserServiceImp在之前,用户的需求可能会影响原来的代码。使用一个set。public void setUserDao(UserDao userDao){ this.userDao = userDao;}之前是主动创建对象,控制

  • emule最新服务器地址,关于emule 服务器列表

    emule最新服务器地址,关于emule 服务器列表关于emule服务器列表我给你几个服务器列表吧。打开选项—务器。然后点右边的“列表”。把以下网址复制进去,保存。然后把启动时自动更新服务器列表连接到服务器时更新服务器列表安全连接打上勾。所谓静态服务器,就是你把服务器优先值设定为高,然后下次登录时系统会自动先尝试你选定的服务器。Kad网络(KadNetwork)是一个完全分散的文件共享网络,它不被中心服务器使用。它执行KademliaP2P…

  • Spark Standalone模式 高可用部署

    Spark Standalone模式 高可用部署

    2021年11月27日
  • leetcode 两数相加_leetcode数组交集

    leetcode 两数相加_leetcode数组交集原题链接给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外,这两个数都不会以 0 开头。示例 1:输入:l1 = [2,4,3], l2 = [5,6,4]输出:[7,0,8]解释:342 + 465 = 807.示例 2:输入:l1 = [0], l2 = [0]输出:[0]示例 3:输入:l1 = [9,9,9,9,9,9

  • 记录下关于调用RAR解压缩的问题

    记录下关于调用RAR解压缩的问题

  • 标准网页两侧浮动广告代码,支持FF及IE

    标准网页两侧浮动广告代码,支持FF及IE点击这里使用RSS订阅本Blog:网页两侧浮动广告代码经测试支持IE、Firefox等浏览器符合标准的正常工作的对联广告lastScrollY=0;functionheartBeat(){vardiffY;if(doc

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号