【题解】EOJ-3479 现任总统的巡游
题目
http://acm.ecnu.edu.cn/problem/3479/
题意
在一个有向图中,求从结点 1 出发经过结点 2 最后回到结点 1 最少经过几个点。
题解
- 观察 1:$1 \rightarrow 2$ 和 $2 \rightarrow 1$ 来回两趟各自不会经过同一个点。
- 观察 2:重复利用的点在路径的交叉处,可能是一个点,也可能是一条路径。
- $dp[x][y]$ 为从 $1$ 出发,两个点分别走正向边到 $x$ 以及走反向边到 $y$,经过最少的点的个数。
- 设原图为 $G(V,E)$,$dist[i][j]$ 为 $i$ 到 $j$ 最短路的长度,建一个新图 $G’(V’,E’)$ 用于状态转移,$dp[x][y]$ 对应结点 $(x,y)$。
- $\forall t \in V, \forall (u,v) \in E: ((u, t), (v, t)) \in E’ \land ((t, v), (t, u)) \in E’$,对应的是两个点中的某个点在原图上走一步,所以边权等于原边权,此时还没有考虑点重复利用的情况。
- 考虑点的重复利用 $(a \neq 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 |
|