【题解】P3953 [NOIP2017 提高组] 逛公园

· · 题解

提供一种缩点+ 拓扑排序+ DP的做法：

考虑将所有边权为 0 的边加入一张新图跑强连通分量缩点，处理出所有 0 环，缩点之后的图一定不存在 0 环。

用 \text{dijkstra} 跑出点 1 到其他所有点的最短路 dist[i]。

定义边 (u,v,w) “在最短路中”当且仅当满足 dist[u] + w = dist[v] 。

因为不存在负权、零环、因此将所有“在最短路”中的边建图后一定是个 DAG，并且拓扑序满足对于任意边 (u,v,w) ，dist[u] + w = dist[v] ，u 一定在 v 之前。

对建出的 \text{DAG} 跑拓扑排序得出拓扑序。

令 f[i,j] 为从 1 到点 i 长度为 dist[i] + j 的路径条数，按照拓扑序顺序 DP：

考虑 f[u,j] 如果从点 v 转移过来，如果这个状态是 f[v,x] 那么一定有

那么有 $x = dist[u]+j - (dist[v] + w)$ 。 且满足 $dist[u] - (dist[v] + w) \le 0$。 若 $x < 0$ ，那么该状态一定为非法状态（不存在比最短路还短的路径），对于合法状态一定有 $x \le k$。 tips: 在 dp 的时候顺便判一下有没有解（如果状态 $f[x,j]$ 可以从状态 $f[v,x]$ 转移过来且 $f[v,x]$ 这个状态是 $\text{inf}$ 的话那么 $f[x,j]$ 也是 $\text{inf}$，如果连通分量大小 >1 那么如果存在一条从 $1$ 到这个连通分量长度为 $x$ 的路径那么一定有 $f[v,x] = \text{inf}$ ）。 复杂度 $O(n\log (n+m) + k(n+m))$ 。 可过 uoj hack数据。 [uoj提交记录](https://uoj.ac/submission/507776)