自动搬运

查看原文

来自洛谷，原作者为

	jimmywang 基环内向树，二维前缀和，三碳化四铝，闪电五连鞭

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

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

以下是正文

远没有 2800。

这个输出，长的十分像必经、非必经、必不经。考虑往网络流上靠。

我们建三层点。第一层是第一组条件，第二层是 $1 \sim n$ 这 $n$ 个人，第三层是第二组限制条件。

以第一组限制条件（$m$ 个数）为例，对于每个数，我们把他连向他可能对应的所有人。如果这个数 $x$ 不是 -1，那么就对应 $x$ 这个人；否则对应的是一段区间（指的是第一个排列里的一段区间）的人。

第二组限制条件同理，只不过变成人连向这些数。

具体的，考虑如下例子：

5
1 2 3 4 5
3 2 4 1 5
3
1 -1 4
-1 -1 1

我们建的图如下（边权 = 流量）：

括号和中括号只是为了点不重复。

然后确定连向 $1 \sim n$ 的必经边 / 非必经边 / 必不经边即可。

但是这样建图边数可能平方，怎么办呢？你发现连续的 -1 的连边状态是一样的，我们可以把他们捏成一个点，然后就好了。