有 nnn 个物品,还有 mmm 条限制,第 iii 条形如 SiS_iSi 中的物品必须被划分到 AAA 中,且 TiT_iTi 中的物品必须被划分到 BBB 中。试将 nnn 个物品划分成两个不交的集合 AAA 和 BBB,最大化满足的限制数。
不保证 Si∪Ti=US_i\cup T_i=USi∪Ti=U,其中 UUU 表示 nnn 个物品构成的集合。
想知道有没有多项式时间复杂度的做法。