floyd – Tgotp-Blog

4898: [Apio2017]商旅

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

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

c++代码如下:

Read more

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路

随便跑跑floyd,然后按顺序相加即可。

c++代码如下:

 

1706: [usaco2007 Nov]relays 奶牛接力跑

令f[q][x][y] 表示x 到 y点经过了2^q个跑道的最小花费,那么把n二进制拆分,

令g[i][j]表示i到j的最小花费,对于n&(1<<q)的部分直接将f[q]加入g中,因为一定从g和f中各挑一半,那么用临时数组h来存储当前答案,最后把再把h重新赋给g。

同[......]

Read more

2165: 大楼

对于这道题,观察n得范围 <= 100 那么考虑倍增Floyd

d[z][x][y] 表示x ,y 跳了2^z次方次所上升得楼层。

对于不连通得两点令d[0][x][y]  = -inf。然后倍增。

对于当前倍增后如果值大于m就跳出,类似于倍增求lca,所以最后答案应该 +[......]

Read more

P2538 [SCOI2008]城堡

爆搜 + 贪心 + 二分 + floyd;

记住:大胆假设,不用证明

先存图,观察数据范围n <= 50 ,直接用floyd求出最短路。

继续二分最大长度 c ,对于每个已有城堡的城市,直接去标记其能到达的城市,然后对于不能到达的,

我们将其距离不超过枚举的c的点期望[......]

Read more