← 返回题目列表

AtCoder · awc0052_d

D. 病毒测试和感染终端

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

Takahashi 是公司网络的管理员。网络有 N 连接到它的终端,编号从 1 to 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 (“检测到感染”):该集合包含 至少一个 受感染的终端。
  • R_j = 0 (“无感染”):该套装包含 no 受感染的终端。

请注意,不同扫描检查的终端组可能重叠,甚至相同。

这里,将每个终端分配“感染”或“未感染”的方法称为 感染状态分配。据说有一个作业是 与所有扫描结果一致 如果,对于每次扫描 j (1 \leq j \leq M),满足以下条件:

  • 当 选择 R_j = 1:集合中 \{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\},至少有一个终端被指定为受感染。
  • 当 选择 R_j = 0:集合中 \{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\},没有指定为受感染的终端。

保证至少存在一个与所有扫描结果一致的分配。在所有此类分配中,找到受感染终端的最少数量。

约束

  • 1 \leq N \leq 16
  • 1 \leq M \leq 100
  • 1 \leq K_j \leq N (1 \leq j \leq M)
  • 1 \leq S_{j,k} \leq N (1 \leq j \leq M, 1 \leq k \leq K_j)
  • 对于每次扫描 j,值 S_{j,1}, S_{j,2}, \ldots, S_{j,K_j} 都是不同的。
  • R_j \in \{0, 1\} (1 \leq j \leq M)
  • 至少存在一种与所有扫描结果一致的感染状态分配。
  • 所有输入值均为整数。

输入

N M
K_1 S_{1,1} S_{1,2} \ldots S_{1,K_1} R_1
K_2 S_{2,1} S_{2,2} \ldots S_{2,K_2} R_2
\vdots
K_M S_{M,1} S_{M,2} \ldots S_{M,K_M} R_M
  • 第一行包含终端数量 N 和扫描次数 M,用空格分隔。
  • 以下各项 M 线, j- 第行 (1 \leq j \leq M),包含扫描信息 j:要检查的终端数量 K_j,端子号 S_{j,1}, S_{j,2}, \ldots, S_{j,K_j},结果 R_j,按此顺序,用空格分隔。

输出

在一行中打印与所有扫描结果一致的所有感染状态分配中受感染终端的最小数量。


示例输入 1

3 2
2 1 2 1
2 2 3 0

示例输出 1

1

示例输入 2

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

示例输出 2

2

示例输入 3

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

示例输出 3

2