【题解】EOJ-3479 现任总统的巡游
题目
http://acm.ecnu.edu.cn/problem/3479/
题意
在一个有向图中,求从结点 1 出发经过结点 2 最后回到结点 1 最少经过几个点。
题解
- 观察 1:1 → 2 和 2 → 1 来回两趟各自不会经过同一个点。
- 观察 2:重复利用的点在路径的交叉处,可能是一个点,也可能是一条路径。
- dp[x][y] 为从 1 出发,两个点分别走正向边到 x 以及走反向边到 y,经过最少的点的个数。
- 设原图为 G(V, E),dist[i][j] 为 i 到 j 最短路的长度,建一个新图 G′(V′, E′) 用于状态转移,dp[x][y] 对应结点 (x, y)。
- ∀t ∈ V, ∀(u, v) ∈ E : ((u, t), (v, t)) ∈ E′ ∧ ((t, v), (t, u)) ∈ E′,对应的是两个点中的某个点在原图上走一步,所以边权等于原边权,此时还没有考虑点重复利用的情况。
- 考虑点的重复利用 (a ≠ b)
- 情况 1:重复利用的恰好是一个点。(a, b) 与 (a, a) 和 (b, b) 连一条长度为 dist[a][b] − 1 的边。
- 情况 2:重复利用的是一条路径。(a, b) 与 (b, a) 连一条长度为 dist[a][b] − 1 的边。
- 为什么要分两种情况呢?因为害怕从 (a, a) 到 (a, a) 之间有负权边。也可以不分开讨论,只要那条 -1 的边不会重复经过就行了。
- 正确性如何保证?对于所有可能的路径交叉,都存在一种方案能够转移到。把交叉的部分看做是两个点交换位置,而两个点以及之间的点都重复利用了一次。同时根据最开始的观察,不可能有点被重复利用超过两次,因此没有后效性。
- 最后就是求 (1, 1) 到 (2, 2) 的最短路,代码中用的是 spfa。
代码
1 |
|
再贴一份稍作修改后的 ultmaster 的代码。
1 |
|