腾飞计划寒假第八课——图论 2025/2/9

今天洛谷讨论区没了

但是 zhhhh 还可以发

吓我一跳

那还行

多源最短路，从所有终点开始跑，给每条边建反边，dijk 初始时把所有终点都放到堆里开始 bfs。

一个点从堆中取出来一次，就把当前走的最短的路封掉，怪物数量减 $1$，continue 掉，不再去更新后面的点。直到没有怪物了就走。

枚举一下用了几天，如果 $c=1$ 的情况，堆旅行一天就多花 $2T+1$，而多一天的收益最多 $1000$，所以天数最多 $500$。

$d_{x,i}$ 表示用 $i$ 天到了 $x$ 点的最大收益。

分层图最短（长）路。

每条边的边权等于到的点的点权。

每天是一层，每个点连向下一层的去的点，最后求 $\max(d_{i,1})$。

发现这个分层图每层内部没有环，所以可以直接 DP。

对每个点记 $d_{x,i}$，表示表示跑到第 $i$ 个点，途经 $h$ 值之和为 $j$ 的最短路径。

分成 $k$ 层跑最短路即可。

相当于 $m-k$ 次不限速机会。

$d_{x,i,j}$ 表示用 $i$ 次不限速，闯了 $j$ 次黄灯到了 $x$ 的时间。

到一个点讨论灯的状态，如果是黄灯可以等或不等。

根据闯黄灯的次数和用的不限速次数分层。

不用分很多层，不用复制边，只需要更新 $dp$ 数组的下一维就行了。

把 $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}$ 是答案。

两层图，一层全 $0$，一层全 $1$，将有开关的点对两层都连边，没开关的点就只连一层。再跑最短路。

可以用 florrid 来做

先把点权离散化一下。

$f_{k,i,j}$ 表示用前 $k$ 小的（小于等于 $k$ 的）点中转，$i$ 到 $j$ 的最短路。

$s$ 到 $t$ 路径上的最大值 $m$，答案就是 $f_{m,s,t}+m$。

枚举从 $1$ 到 $n$ 的最小流量。

维护一个图，每次加边，没加一次边重跑一次最短路。

最多加 $m$ 次边，总复杂度 $O(m^2\log n)$。

如果两人到达同一个点，那么一定是按照最短路直接走到终点。

也就是只有一开始 $b$ 没有动的一段需要考虑，后面答案是一定的。

所以所有有效状态是 $O(n)$ 的，预处理 $b$ 和 $n$ 号点所有点的最短路之后，使用 dijk 计算即可。

$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$。

差分约束求解。

tarjan 缩点之后跑一个拓扑，拓扑过程中 dp。