腾飞计划寒假第八课——图论 2025/2/9
Lovely_yhb
·
·
个人记录
今天洛谷讨论区没了
但是 zhhhh 还可以发
吓我一跳
那还行
P9650 [SNCPC2019] Escape Plan
多源最短路，从所有终点开始跑，给每条边建反边，dijk 初始时把所有终点都放到堆里开始 bfs。
一个点从堆中取出来一次，就把当前走的最短的路封掉，怪物数量减 1，continue 掉，不再去更新后面的点。直到没有怪物了就走。
P6005 [USACO20JAN] Time is Mooney G
枚举一下用了几天，如果 c=1 的情况，堆旅行一天就多花 2T+1，而多一天的收益最多 1000，所以天数最多 500。
分层图最短（长）路。
每条边的边权等于到的点的点权。
每天是一层，每个点连向下一层的去的点，最后求 $\max(d_{i,1})$。
发现这个分层图每层内部没有环，所以可以直接 DP。
### [P9813 [CCC 2015 S4] Convex Hull](https://www.luogu.com.cn/problem/P9813)
对每个点记 $d_{x,i}$，表示表示跑到第 $i$ 个点，途经 $h$ 值之和为 $j$ 的最短路径。
分成 $k$ 层跑最短路即可。
### [P9549「PHOI-1」路虽远](https://www.luogu.com.cn/problem/P9549)
相当于 $m-k$ 次不限速机会。
$d_{x,i,j}$ 表示用 $i$ 次不限速，闯了 $j$ 次黄灯到了 $x$ 的时间。
到一个点讨论灯的状态，如果是黄灯可以等或不等。
根据闯黄灯的次数和用的不限速次数分层。
不用分很多层，不用复制边，只需要更新 $dp$ 数组的下一维就行了。
### [P9751 [CSP-J 2023] 旅游巴士](https://www.luogu.com.cn/problem/P9751)
把 $k$ 作为分层图第二维。
$f_{i,x}$ 表示走到 $i$，$t\mod k=x$ 用的时间。
相当于 $k$ 层图。
如果到达这个点的时候边已经打开了，就可以用 $f[i][x]+1\rarr f[j][(x+1)\mod k]$。
否则算一下等到开放需要多久 $\displaystyle\lceil\frac{w−p}{k}\rceil\times k+p+1$。
$f_{n,0}$ 是答案。
### [[ABC277E] Crystal Switches](https://www.luogu.com.cn/problem/AT_abc277_e)
两层图，一层全 $0$，一层全 $1$，将有开关的点对两层都连边，没开关的点就只连一层。再跑最短路。
### [P2966 [USACO09DEC] Cow Toll Paths G](https://www.luogu.com.cn/problem/P2966)
可以用 florrid 来做
先把点权离散化一下。
$f_{k,i,j}$ 表示用前 $k$ 小的（小于等于 $k$ 的）点中转，$i$ 到 $j$ 的最短路。
$s$ 到 $t$ 路径上的最大值 $m$，答案就是 $f_{m,s,t}+m$。
### [P5837 [USACO19DEC] Milk Pumping G](https://www.luogu.com.cn/problem/P5837)
枚举从 $1$ 到 $n$ 的最小流量。
维护一个图，每次加边，没加一次边重跑一次最短路。
最多加 $m$ 次边，总复杂度 $O(m^2\log n)$。
### [P9724 [EC Final 2022] Chase Game](https://www.luogu.com.cn/problem/P9724)
如果两人到达同一个点，那么一定是按照最短路直接走到终点。
也就是只有一开始 $b$ 没有动的一段需要考虑，后面答案是一定的。
所以所有有效状态是 $O(n)$ 的，预处理 $b$ 和 $n$ 号点所有点的最短路之后，使用 dijk 计算即可。
### [P5590 赛车游戏](https://www.luogu.com.cn/problem/P5590)
$d_u$ 表示从 $1$ 到 $u$ 的最短路径，对于所有边都有 $w_{u,v}=d_v-d_u$。
与其设置边权使路径长度相等，不如设置路径长度去拟合边权的限制。
$1\le d_v-d_u\le9$ 转化为 $d_v\le d_u+9,d_u\le d_v-1$。
差分约束求解。
### [P3436 [POI 2006] PRO-Professor Szu](https://www.luogu.com.cn/problem/P3436)
tarjan 缩点之后跑一个拓扑，拓扑过程中 dp。