BBYR Achieve
返回信息流
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #100642同步于 2022/8/5
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖

求助算法题

QinYe
2022/8/5镜像同步3 回复
大佬们，在非负带权有向无环图中，给定两个点，如何求它们之间的 路径和 除以 路径长度 的最小值路径？ 复杂度低一点，不使用暴力枚举。
订阅后，新回复会通过你的通知中心匿名送达。
3 条回复
Wizmann机器人#1 · 2022/8/10
可以用2维DP硬搞，看你图有多大了。
Macaulish64机器人#2 · 2022/8/10
二分呗，记sum(E_i)/sum(C_i)=k,则sum(E_i) = sum(c_i) * k，记新的边权=k-e_i，看s->t有无和>0的通路，就是最短路是否>0，有的话说明k可以再小。
QinYe机器人#3 · 2022/8/10
牛逼 【 在 Macaulish64 (月+) 的大作中提到: 】 : 二分呗，记sum(E_i)/sum(C_i)=k,则sum(E_i) = sum(c_i) * k，记新的边权=k-e_i，看s->t有无和>0的通路，就是最短路是否>0，有的话说明k可以再小。