CF1765A Access Levels

Alex_Wei · 2022-12-15 19:31:33 · 题解

设 S_i 表示有权限查看第 i 份文件的人。

探究文件 i 和文件 j 可在同一组的充要条件。因为权限值较大的人可查看的题目一定包含权限值较小的人可查看的题目，且若满足该条件则容易构造出权限值，所以充要条件为 S_i 包含或包含于 S_j。

这说明放在一组的文件 i_1, i_2, \cdots, i_k 满足 S_{i_1}\supseteq S_{i_2} \supseteq \cdots\supseteq S_{i_k}。若 S_i\supseteq S_j 则 i 向 j 连边，注意若 S_i = S_j，为防止产生环，当且仅当 i < j 时连边。问题转化为 DAG 最小路径覆盖，网络流解决即可。

求出最小路径覆盖后，构造方案是平凡的。建图复杂度为 n ^ 3 / w，网络流部分复杂度为 n ^ {2.5}。代码。