自动搬运

查看原文

来自洛谷，原作者为

	enucai Remake.

搬运于2025-08-24 22:52:52，当前版本为作者最后更新于2023-12-06 10:19:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

大家好像都在写 $O(n3^k)$，呃呃。

首先最大流转成最小割，考虑状压，令 $f_{i,S}$，表示考虑了 $[1,i]$ 这些点，源点仅能走到点集 $S$ 中的点，最小割掉的边权总和。

由于有 $u\to v$，$v-u\le k$，所以对于 $S$，我们只需要保留 $[i-k+1,i]$ 这个区间内的点即可，因为前面的点都不可能走到 $>i$ 的点。

转移时暴力枚举子集是 $O(n3^k)$ 的，但是发现如果最终能走到 $i$，那么所有 $x\to i$ 的边都不割是最优的，否则就得割掉所有 $S$ 集合中 $x\to i$ 的边，复杂度 $O(n2^k)$。