题目描述

高桥君是企业网络管理员。网络中有 $N$ 台终端，编号 $1$ 到 $N$。每台终端处于"感染"或"未感染"两种状态之一，但高桥君不知道哪些终端被感染。

高桥君执行了 $M$ 次扫描。每次扫描 $j$（$1 \leq j \leq M$）同时检测指定的 $K_j$ 台终端集合 $\{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\}$，返回结果 $R_j$：

• $R_j = 1$（"检测到感染"）：集合中至少有 1 台感染终端。
• $R_j = 0$（"无感染"）：集合中没有感染终端。

注意：不同扫描的检测集合可能重叠，甚至完全相同。

将每台终端分配为"感染"或"未感染"的方法称为感染状态分配。一个分配与所有扫描结果一致，当且仅当对所有扫描 $j$（$1 \leq j \leq M$）满足：

• 当 $R_j = 1$ 时：集合中至少有 1 台被分配为感染。
• 当 $R_j = 0$ 时：集合中没有终端被分配为感染。

保证至少存在一个与所有扫描结果一致的分配。在所有满足条件的分配中，求感染终端数量的最小值。

输入格式

第一行两个整数 $N, M$。

接下来 $M$ 行，每行格式为 $K_j\ S_{j,1}\ S_{j,2}\ \ldots\ S_{j,K_j}\ R_j$，表示一次扫描。

输出格式

输出一个整数，表示所有与扫描结果一致的分配中，感染终端数量的最小值。

3 2
2 1 2 1
2 2 3 0

1

5 4
3 1 2 3 1
2 4 5 1
2 1 4 0
2 2 5 1

2

8 5
4 1 2 3 4 1
4 5 6 7 8 1
4 1 3 5 7 1
4 2 4 6 8 0
4 3 4 7 8 1

2

数据范围

• $1 \leq N \leq 16$
• $1 \leq M \leq 100$
• $1 \leq K_j \leq N$
• $1 \leq S_{j,k} \leq N$
• 每次扫描中，$S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}$ 互不相同
• $R_j \in \{0, 1\}$
• 保证至少存在一个与所有扫描结果一致的分配
• 输入均为整数

提示

本题考查状态压缩。由于 $N \leq 16$，可以用一个 $N$ 位二进制数表示所有终端的感染状态。

对于每个扫描，将检测集合转换为位掩码。然后枚举所有可能的感染状态（$0$ 到 $2^N - 1$），检查是否与所有扫描结果一致，记录满足条件的最小感染数。

时间复杂度 $O(2^N \cdot M)$，空间复杂度 $O(M)$。

来源

AtCoder AWC 0052D