AC. 梦想

frank_c1

[APIO 2015] Jakarta Skyscrapers

发布于2017年04月16日 | 暂无评论 | 371阅读 | 最短路径

题意简述

n个点和m只doge。

i只doge在x_i位置,跳跃能力为v_i

设在某时刻,第i只doge在点p,它能够

1. 跳到p - v_ip + v_i(若存在)。

2. 把携带的消息告诉在这个点的doge。

现在第0只doge有一条消息,求所有doge总共最少跳跃多少步能够将消息传达到第1只doge呢?

1 \le n, m \le 30000

算法讨论

考虑暴力。如果有一只携带消息的doge来到了点x,那么所有原来在点x上的doge就可以去更新所有能到达的位置,对于第i只doge,它就能去更新所有形如x_i + kv_i \; (k \in Z)的位置。这是一个最短路的过程。

但是,我们发现当v_i很小时,连出的边将非常多。这种算法最坏会产生O(n ^ 2)条边。

另一个角度看,当v_i较大时,连出的边是比较稀疏的。我们不妨进行分段,设常数C,对于v_i \gt C的doge,我们暴力连边。现在我们只要着手优化v_i较小的情况即可。

v_i较小有什么性质呢?我们发现,这时步长就十分有限了,只有C种。

我们不妨对每个点建C个额外点,设第i个点的第j个额外点为P_{i,j}。我们在P_{i,j}P_{i+j,j}连长度为1的边,再由所有P_{i,j}i连长度为0的边。对于v_i \le C的doge,我们就由x_iP_{x_i, v_i}连长度为0的边即可。

整理一下所有的花费,点数是O(nC),边数是O(nC + m \frac{n} {C})

边数中O(nC)的边显然不会成为瓶颈,另外我们默认n,m同阶,于是点数是O(nC),边数是O(n ^ 2 \frac{1} {C})

若用Fibonacci堆优化dijkstra,则简单计算一下可以发现当C\sqrt{\frac{n} {\log n}}时复杂度达到最优。总时间复杂度O(n \sqrt{n \log n})

(我只写了堆优化,复杂度似乎有点不对?但还是比C\sqrt{n}时跑得快一点。