自动搬运

查看原文

来自洛谷，原作者为

	sidekick257 你是向日葵派，还是蒲公英派？

搬运于2025-08-24 23:08:27，当前版本为作者最后更新于2025-01-11 20:15:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$\min$ 是假的，相当于两个图，并且与和或本质相同，只考虑或即可。

使用一次普通列车是可以用 sosdp 简单解决的。

有个我不会证的性质，就是最多使用普通列车最多 $O(k)$ 次，至少我只能造出 $O(k)$ 次的数据，如果有更强的数据欢迎联系我。

基于这个性质有一个做法，就是每次每次跑完 dij 做一次 sosdp，总共进行 $O(k)$ 次。

复杂度 $O(k((n+m)\log(n+m)+3^k))$，无法通过。

考虑优化建图，把 sosdp 的方式刻画在图上。

图 $1$ 的 $i$ 连到超集，边权为 $0$。

图 $2$ 的 $i$ 连到子集，边权为 $0$。

图 $1$ 的 $i$ 连到图 $2$ 的 $i$，边权为 $a_i$。

原图的 $i$ 连到图 $1$ 的 $c_i$，边权为 $0$。

图 $2$ 的 $x$ 连到所有 $c_i=x$ 的原图的 $i$，边权为 $0$。

直接跑 $dij$ 即可。

复杂度 $O((3^k+n+m)\log (3^k+n+m))$，无法通过。

把上面那个做法的 sosdp 换成 fwt 即可。

复杂度 $O(k2^k+n+m\log (k2^k+n+m))$。

可能略微卡常，因为上一种做法跑的有点快了。

直接一提的是使用 fib 堆优化可以做到更优的复杂度 $O((2^k+n)\log (2^k+n)+k2^k+m)$，但是跑的更慢。