最新要闻
- 焦点精选!英国工程师警告:电动车可能导致停车场坍塌 原因意想不到
- 全球新动态:荣耀平板V8 Pro预装MagicOS 7.0 赵明:跨设备非常强 将与苹果竞争
- 天天微头条丨我国成功发射高分十一号04星 首次实现中继星数据双向高速互传
- 太阴间了!荷兰一车企推出特斯拉Model 3定制灵车
- 环球热头条丨荣耀赵明:荣耀笔记可记录瞬间灵感 未来将在多端流转
- 焦点速讯:2.4折发车:361° 新款休闲老爹鞋99元官方大促
- 谷歌旗舰Pixel 7遭品控问题:带壳使用后摄玻璃依旧碎裂
- 焦点热议:驾校学车被撞伤获赔23万 学员用不用担责?法院如此判决
- 环球热讯:奔驰GLS国产平替 北京越野BJ90山河经典版上市:47.80万起
- 观热点:纽约州进入紧急状态 美国暴风雪有多可怕?官方告诫市民别出门否则会冻死
- 快消息!稳住iPhone 14 Pro 富士康给员工发留任奖金:最高5000元
- 黑客携4亿推特用户数据勒索马斯克:想破财消灾还是被罚款?
- 世界看点:驾特斯拉Model X车祸 5个多月林志颖仍在康复:期待复工
- 一家三口发烧用洋葱退热成功 医生科普:低烧有用、高烧不建议
- 【全球新视野】工信部拟规定:APP应可便捷卸载 不得默认自动续订
- 当前关注:终于不用费劲算优惠了:天猫年货节取消跨店满减 直接降价
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
焦点热议:AcWing361. 观光奶牛
传送门
题目描述
给定一张 \(L\) 个点、\(P\) 条边的有向图,每个点都有一个权值 \(f[i]\),每条边都有一个权值 \(t[i]\)。
求图中的一个环,使“环上各点的权值之和”除以“环上各边的权值之和”最大。
(资料图片仅供参考)
输出这个最大值。
注意:数据保证至少存在一个环。
输入格式
第一行包含两个整数 \(L\) 和 \(P\)。
接下来 \(L\) 行每行一个整数,表示 \(f[i]\)。
再接下来 \(P\) 行,每行三个整数 \(a,b,t[i]\),表示点 \(a\) 和 \(b\) 之间存在一条边,边的权值为 \(t[i]\)。
解题思路
\(\qquad\)这题要让一个\(\LARGE \frac{\sum f}{\sum t}\)最大化,所以是一个\(01\)分数规划问题,对于\(01\)分数规划,我们可以采用二分求解(实数)。我们二分的目标是最后的答案\(ans\),在check(x)
函数中,有一下\(2\)种情况:
\(\qquad\quad\)\(a.\)当\(mid < ans\)的时候,说明一定有一个环的\(\Large \frac{\sum f}{\sum t} > mid\),我们对这个公式进一步推导:
\(\qquad\qquad\qquad\qquad\Large \sum f > \sum t \times mid\)
\(\qquad\qquad\qquad\qquad\Large \sum f - \sum t \times mid > 0\)
\(\qquad\qquad\qquad\qquad\Large \sum (f-mid\times t) > 0\)
正好我们这张图有个不好处理的条件,也就是点权,我们在这里只要把点权移到边上,使得每条边的权重变为\(f-mid\times t\),那我们就可以跑个正环就结束了。这里采用\(dfs\)版的\(SPFA\)判环,实测只要\(20ms\)当然,要跑负环也很容易,只要把上式进行一定的变形:
\(\qquad\qquad\qquad\qquad\Large \sum (mid\times t-f) < 0\)
这样把边权处理成\(mid\times t - f\)就可以跑负环了。
代码
#include #include using namespace std;const int N = 1010, M = 5050;int h[N], e[M], ew[M], vw[N], ne[M], idx;double dist[N]; int st[N], ring, n, m;void add(int a, int b, int c){ e[idx] = b, ne[idx] = h[a], ew[idx] = c, h[a] = idx ++ ;}void dfs(int cur, double x) { st[cur] = 1; for (int i = h[cur]; ~i; i = ne[i]) { int j = e[i]; double w = vw[cur] - ew[i] * x; if (dist[j] < dist[cur] + w) { dist[j] = dist[cur] + w; if (st[j] == 1) { ring = true ; break ; } dfs(j, x); if (ring) return ; } } st[cur] = 114514;}bool check(double x) { memset(st, 0, sizeof st); ring = 0; for (int i = 1; i <= n; i ++ ) { if (st[i]) continue ; if (ring) break ; dfs(i, x); } return ring;}int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%d", &vw[i]); memset(h, -1, sizeof h); while (m -- ) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add(u, v, w); } double l = 1, r = 1000; while (r - l > 1e-3) { double mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; } printf("%.2lf\n", l); return 0;}
-
即时:10 种超好用的 MyBatis 写法,同事都说好用!
作者:smile_lg来源:blog csdn net smile_lg article details 71215619用来循环容器的标签forEac...
来源: -
Atcoder Grand Contest AGC 060 D Same Descent Set 题解 (容斥,多项式)
题目链接计数技巧大杂烩,好题先来定义一下"间隔",间隔指的是两个相邻的数之间的大小关系,有两种状态...
来源: 焦点热议:AcWing361. 观光奶牛
即时:10 种超好用的 MyBatis 写法,同事都说好用!
焦点!【记录贴】项目经理的进阶日常:靠年终总结获得了核心项目的机会
Atcoder Grand Contest AGC 060 D Same Descent Set 题解 (容斥,多项式)
焦点精选!英国工程师警告:电动车可能导致停车场坍塌 原因意想不到
全球新动态:荣耀平板V8 Pro预装MagicOS 7.0 赵明:跨设备非常强 将与苹果竞争
天天微头条丨我国成功发射高分十一号04星 首次实现中继星数据双向高速互传
太阴间了!荷兰一车企推出特斯拉Model 3定制灵车
环球热头条丨荣耀赵明:荣耀笔记可记录瞬间灵感 未来将在多端流转
Java基本数据类型
环球焦点!易基因|深度综述:癌症中RNA修饰机制的遗传和表观遗传失调(m6A+m1A+m5C+ψ)
焦点速讯:2.4折发车:361° 新款休闲老爹鞋99元官方大促
谷歌旗舰Pixel 7遭品控问题:带壳使用后摄玻璃依旧碎裂
焦点热议:驾校学车被撞伤获赔23万 学员用不用担责?法院如此判决
环球热讯:奔驰GLS国产平替 北京越野BJ90山河经典版上市:47.80万起
第五章 --------------------加载和编译XAML
天天短讯!Netty中8大组件详解(EventLoop、Channel、ChannelFuture、Future、 Promise、Handler 、 Pipe
全球热点!贯穿汽车用户全生命周期,火山引擎数智平台能帮车企做这些事!
全球播报:当项目经理看世界杯决赛时…
在Windows中利用WSL2安装禅道17.7
观热点:纽约州进入紧急状态 美国暴风雪有多可怕?官方告诫市民别出门否则会冻死
快消息!稳住iPhone 14 Pro 富士康给员工发留任奖金:最高5000元
黑客携4亿推特用户数据勒索马斯克:想破财消灾还是被罚款?
世界看点:驾特斯拉Model X车祸 5个多月林志颖仍在康复:期待复工
一家三口发烧用洋葱退热成功 医生科普:低烧有用、高烧不建议
【全球新视野】工信部拟规定:APP应可便捷卸载 不得默认自动续订
当前关注:终于不用费劲算优惠了:天猫年货节取消跨店满减 直接降价
最新资讯:雷军刚投的激光雷达:120米以外就能探测到路面轮胎
环球讯息:李国庆称逃离北上广去二线商机无限 快反思降降价:看好杭州合肥长沙等
43mm大喇叭!荣耀亲选迪士尼便携蓝牙音箱上架 149元
天天讯息:从发现SQL注入到ssh连接
学习下Redis内存模型
环球观天下!更冷了!南方多地将有大到暴雪:湿冷“魔法攻击”来了
【世界独家】张艺谋新作 电影《满江红》官宣阵容:沈腾、易烊千玺双男主
每日热闻!专家:波司登万元羽绒服面料很低廉
焦点消息!文化输出网红要复出了?李子柒成子柒文化实控人:微念创始人退出公司
天天快讯:多语种录音转译!讯飞开放式办公耳机iFLYBUDS Air上市 899元
HTC G18上市价格是多少?HTC G18手机参数
小米3什么时候出的?小米3后盖怎么打开?
win7系统怎么设置防火墙?win7系统一键还原按哪个键?
显示器驱动程序停止响应的原因有哪些?电脑显示驱动程序出现问题怎么办?
洗衣机怎么消毒?洗衣机消毒方法有哪些?
科特迪瓦是哪个国家?科特迪瓦特产有哪些?
起初婚礼放鞭炮是为了什么?起初婚礼上放鞭炮是什么原因?
权力的游戏布兰为什么是夜王?权力的游戏布兰的结局是什么?
世界热门:Dubbo 可扩展性设计
Web前端--HTML+Canvas+Js实现3D魔方小游戏
世界观点:微信Native支付(扫码支付)商户配置
魔兽世界里RN是什么意思?魔兽世界RN含义解释
天仙配电视剧大结局是什么?天仙配电视剧演员表
巧克力中的劳斯莱斯是什么牌子?巧克力中的劳斯莱斯多少钱?
淘宝金币有什么用处?淘宝金币怎么抵扣现金?
女生坐位体前屈满分多少厘米?女生坐位体前屈的技巧有哪些?
冯小宁战争三部曲是哪三部?冯小宁战争三部曲观看顺序
春眠不觉晓处处蚊子咬下一句是什么?春眠不觉晓改编打油诗
每日快报!年度必看神作!《阿凡达2》全球票房破9亿美元:内地破7.3亿
3排8座拉全家 路虎卫士130国内预售:119.8万起
新突破!我国建成首个年产500亿立方米特大型产气区
环球观天下!学AMD大涨价!Intel B760新一代平民主板来了 华硕等最快本周出货:涨幅不小
【快播报】教程干货!JNPF快速搭建库存管理与财务管理板块
天天热门:马斯克被曝架子大:访客等1个小时才能见人 还不能先开口
世界热点!“更适合国内路况”的CLTC新标准 为啥更坑“电动爹”了?
今日热搜:PC玩家狂喜:PS3模拟器已可运行所有PS3游戏
一瓶的钱现在买3件!杰威尔男士护肤套装大促:原价100多现在30包邮
环球今日讯!顾客吐槽看《阿凡达2》需30元购3D眼镜 凭啥买非常不合理:影院回应
【环球快播报】【爬虫+数据清洗+可视化分析】舆情分析哔哩哔哩"阳了"的评论
Python爬虫实战,requests+tqdm模块,爬取漫画之家漫画数据(附源码)
上海一车主至少5次倒车撞击后车:后车特斯拉全程不动 网友吐槽
热门:《三体》动画口碑直降!豆瓣跌破6分 网友发现人脸模型重复利用
讯息:5MHz处理器+128MB内存:成功运行Win7旗舰版
天天百事通!2022年度七大叫好又叫座游戏 看完手痒别怪我
观察:苹果中国开启新年福利:iPhone 13等降价优惠千元!
当前速看:Ubuntu下的NVIDIA显卡【驱动&CUDA 安装与卸载】
韩国报告首例“食脑虫”病例:一天即死亡、不会人传人
快报:葛优母亲施文心去世:享年94岁 从事电影文学编辑30年
【环球新视野】《西游记之七十二变》终极预告:孙悟空、牛魔王一起学法术
每日讯息!EPIC喜加一:国产之光3A游戏《暗影火炬城》免费送 省了108元
RTX 4070 Ti跑分偷跑:怎么灭掉了RTX 3090 Ti!
滚动:在虚幻引擎中使用蓝图实现简单的对话
每日视讯:Wi-Fi 6路由杀到169元 荣耀路由X4 Pro发布:三个千兆网口
世界新消息丨豆瓣2022年度电影榜单出炉:《阿凡达2》入榜
天天热资讯!虚假新闻检测(MAC)《Hierarchical Multi-head Attentive Network for Evidence-aware F
天天讯息:Atcoder Beginner Contest ABC 283 Ex Popcount Sum 题解 (类欧几里得算法)
环球微资讯!一群环保人士 为何想限制游戏发展?
热资讯!首发199元 荣耀手环7发布:1.47英寸大屏 支持全天候血氧监测
韩国人造肉需求激增:近一半韩国年轻人买过吃过人造肉
02年小伙3年打6份工买车 正能量感染网友:送过外卖、做过服务员等
首发5680元 汉王N10 Max墨水平板发布:13.3英寸大屏
微头条丨失业率最高的西班牙:开始薅中国羊毛
短讯!JMeter
第四章 --------------------XAML名称空间
环球观察:快2023年了还有友商拿8+128卡位凑数 一加11直接12G起步:欢迎友商跟进
天天新消息丨纯可可脂 怡浓55%-100%黑巧克力35元起
N多玩家插反PS5游戏盘!官方发文纠正
环球聚焦:功耗高、死机!AMD正在拼命优化RX 7900驱动
男子自曝无聊送外卖结果2小时挣150 网友质疑摆拍:根本没地方停车
天天消息!AcWing. 1146 新的开始
C919起飞验证!波音、中国商飞新合作:开发全新飞机材料
全球热点!20000转风扇看得见!红魔8 Pro+氘锋透明版图赏
全球头条:想堵车都难 福特车路协同系统落地国内六城