最小环 – Tgotp-Blog

4898: [Apio2017]商旅

发现实际上把每个物品提出来做最短路后,可以转化为一个在图中求 最小的 \frac{\sum{w}}{\sum{time}} 的环

上面那东西就是个01规划搞搞就行了,然后最小环直接套floyd即可

c++代码如下:

Read more