CF2052 (NERC 2024Final) K Knowns and Unknowns

· · 题解

远没有 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 的连边状态是一样的，我们可以把他们捏成一个点，然后就好了。