[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,看下面这个例子:
唯一一种可行的走法是:翻转 \(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)\)。
代码?拜托了,明天的我!
标签:199,删除,P6880,题解,短路,dijkstra,Luogu,JOI,翻转 From: https://www.cnblogs.com/crab-in-the-northeast/p/luogu-p6880.html