【题解】[APIO2017] 商旅 分数规划 floyd luogu – 3778 —quhengyi11

传送门:[APIO2017] 商旅 题意:n 个点 m 条边的有向图,每条边的边权是你走过这条边消耗的时间,你要在上面跑来跑去,你有一个只能装一个物品的背包,现在知道每个点(集市)对于 k 种物品的买入和卖出价(假设没这种物品就为-1),求一条环路使得你的盈利效率最高,盈利效率的定义是 $\frac 阅读更多…