分层图
引入
我们发现,在某些最短路问题中,并不只有一种性质的边,或者说允许改变一些边权。为了处理这样的问题, 分层图建模思想 应运而生。
构建
对于这样的问题,我们考虑根据边的不同性质分别建图,在图的内部则是一些普通边,在图与图之间连上那些 “特殊的性质边”,换句话说,就是将 决策前的状态 和 决策后的状态 之间连接一条 权值为决策代价 的边,表示付出该代价后就可以进行此步状态转移 。
决策,就是分层图的构图依据。
具体的实现有两种:
数组 | 建边 | 特点 | |
---|---|---|---|
方式一:物理构图 | \(dis[N*K]\) | 图内,图间 | 第 \(i\) 张图的起点是(i-1) * n+1 |
方式二:DP构图 | \(dis[N][K]\) | 只有图内,图间由dp决策代替 | \(vis\) 也是二维,多一维模拟层数 |
例题
经典题,\(k\) 层图,图之间有免费边。
关键是寻找分层依据。发现发车间隔 \(k\) 很小,考虑从它下手。假设当前时间为 \(p\), 走到了 \(u\) 点, 到 \(v\) 的边权为 \(w\)。
- 若 \(p < w\), 没办法走。但其实如果在起点多等待几轮就可以通过了。设在多等的时间 \(\Delta t = \frac{\lceil w-p \rceil}{k} \times k\) ,因此真正的时间 \(t = \Delta t + p\)。
- 若 \(p \ge w\),直接走就行。
怎么用 \(u\) 和 \(p\) 来转移呢?我们发现实际的时间并不重要,因为很大一部分多等的时间都可以用 \(k\) 的若干倍轻松统计。于是只需要关心 \(p \mod k\) 就可以啦!,不妨称其为 余数时间。那么定义就有了: \(f[i][j]\) 表示 当前在点 \(i\), 余数时间 为 \(j\) 的 实际时间 的最小值。
- 若 \(p < w\), 有转移 \(dis[v][(p + 1) \mod k] = \min(dis[u][p \mod k], \ p) + 1\) 。
- 若 \(p \ge w\),有转移 \(dis[v][(t + 1) \mod k] = \min(dis[u][t \mod k]+ \Delta t, \ t) + 1\) 。
边界条件: \(dis[1][0] = 0\)。
答案:\(dis[n][0]\)。
总结
个人更喜欢 DP建图, 因为它更突出了 “最短路算法本质是 \(dp\) 的运用”。
参考博客
关于分层图(学了你不吃亏,学了你不上当 雾) - AcWing
图论-分层图详解(附完整代码) - c20251917_lzy - 博客园 (cnblogs.com)
Genius_Star - 题解:CSP-J 2023旅游巴士
标签:决策,分层,时间,Delta,dis,mod From: https://www.cnblogs.com/superl61/p/18430951