• 欢迎光临~

Luogu P6880 [JOI 2020 Final] オリンピックバス 题解

开发技术 开发技术 2022-10-10 次浏览

[P6880 JOI 2020 Final] オリンピックバス - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

两条前置知识:

  • 在图 (G) 上构造根为 (x) 的最短路树 (T),我们删除任意一条不在 (T) 上的边 (e)(x) 到任意一个节点 (u) 的距离 (d(x, u)) 均不会发生变化。
  • 有向图上 (d(i, x)) 的求法,其中 (x) 为定点。实际上就是构造 (G) 的反图,在反图上跑 (x) 为源点的 dijkstra 即可。

这个题我的第一反应是分层图,把原图分为两层然后两层之间用反边单向导通。也就是这个题。

但是这样可以被 hack,看下面这个例子:

Luogu P6880 [JOI 2020 Final] オリンピックバス 题解

唯一一种可行的走法是:翻转 (4 to 3) 这条边,然后 (1 to 2 to 3 to 4 to 5 to 6 to 9 to 8 to 3 to 4 to 7 to 1)

可以看到 (3 to 4) 我们走了两次,分层图不能很好的处理一条道路被翻转然后被走两次(注意到我上面给的另一道题,那个题本身就不允许在一条道路上反走两次,但这个题可以)。

思考发现好像怎么改分层图的模型也不能处理这个问题。先扔在一边。

注意到原题的一个条件:(n le 200)。也就是这个图是稠密的?不过还有一个更强的性质,某棵最短路树最多只有可能有 (199) 条边,剩余的边我们都可以利用前置知识第一条加速计算。

实际上翻转一条边 (e) 可以看做删除 (e) 然后再添加它的反边 (e')

(e) 代表 ((u, v, w))(e') 代表 ((v, u, w))。再设删除 (e)(s, t) 两点最短距离 (d(s, t))(也就是原图上 dijkstra 的结果);删除 (e)(s, t) 两点最短距离为 (f(s, t));删除 (e) 再增加 (e')(1)(n) 的最短路变为 (D)(n)(1) 的最短路变为 (X)

那么有:(D = min(f(1, n), f(1, v) + w + f(u, n)))(X = min(f(n, 1), f(n, v) + w + f(u, 1)))

证明:(min) 中前半部分为不走 (e') 的最短路,后半部分为必走 (e') 的最短路,合并即可。

如何快速求解 (f(s, t))?事实上我们只关心四种 (f)(s = 1)(s = n)(t = 1)(t = n)。我们令 (T)(R) 分别代表根为 (1) 和为 (n) 的两棵最短路树。那么:

  • (e in T) 时,(f(1, v))(f(u, 1)) 需要重新跑 dijkstra 计算;否则 (f(1, t) = d(1, t))(f(s, 1) = d(s, 1))
  • (e in R) 时,(f(n, t))(f(s, n)) 需要重新跑 dijkstra 计算;否则 (f(n, t) = d(n, t))(f(s, n) = d(s, n))

由于 (T)(R) 边数最多只有 (199),因此上述算法中最多会跑 (199 times 2) 次 dijkstra,可过。

最后枚举 (e),求最小的 (D + X + k) 即可,这里 (k) 是原题中的 (D_i):把 (e) 翻转的代价。

稠密图,dijkstra 不加堆优化(不如不加)。

(mathcal{O}(n^3))

代码?拜托了,明天的我!

程序员灯塔
转载请注明原文链接:Luogu P6880 [JOI 2020 Final] オリンピックバス 题解
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com