P9902 『PG2』模拟最大流

enucai · 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)。