分数: 466 分
问题陈述
Takahashi 是一个公司网络的管理员,该网络包括 N 计算机。每台计算机的编号为 1 to N.
发现 此网络中存在 M 类型的计算机病毒。每个病毒的编号为 1 to M.
病毒 j (1 \leq j \leq M)有能力感染一组特定的计算机 S_j. S_j 可能为空。
高桥希望通过划分来减轻损害 N 计算机进入多个子网(组)并安装防火墙以阻止组之间的通信。这里,分组意味着对集合进行划分 N 将计算机分成一个或多个非空组,其中每台计算机都属于一个组。组的数量可以是任意数量 1 to N.
每种病毒的损害根据以下规则独立确定:
- 如果所有计算机都感染病毒 j的感染目标 S_j 属于 同组,病毒 j 在组内传播,不受任何防火墙阻止,且组内所有计算机 S_j 已损坏。
- 如果计算机感染病毒 j的感染目标 S_j 分布在 两个或多个不同组,病毒 j的传播被防火墙阻止,并且没有计算机 S_j 已损坏。
这里,如果 S_j 为空或仅包含一台计算机,所有计算机 S_j 被认为属于同一组。 (如果 S_j 为空,没有计算机损坏。如果 S_j 仅包含一台计算机,无论分组如何,该计算机总是会损坏。)
考虑到所有伤害 M 病毒种类,我们希望尽量减少被一种或多种病毒损坏的计算机数量(即使同一台计算机被多种病毒损坏也算为一台)。
找出选择最佳分组时受损计算机的最少数量。
约束
- 1 \leq N \leq 15
- 1 \leq M \leq 500
- 0 \leq k_j \leq N (1 \leq j \leq M)
- 1 \leq s_{j,i} \leq N (1 \leq j \leq M, 1 \leq i \leq k_j)
- 计算机号码 病毒感染目标中的 s_{j,1}, s_{j,2}, \ldots, s_{j,k_j} 在病毒的感染目标中 j 都是不同的
- 所有输入值均为整数
输入
N M
k_1 s_{1,1} s_{1,2} \ldots s_{1,k_1}
k_2 s_{2,1} s_{2,2} \ldots s_{2,k_2}
\vdots
k_M s_{M,1} s_{M,2} \ldots s_{M,k_M}
- 第一行包含 N,计算机数量,以及 M,病毒类型数量,以空格分隔。
- 以下 M 行提供有关每种病毒的信息。
- 的 (1 + j)第行包含 k_j,病毒感染目标计算机数量 j,后跟计算机编号 s_{j,1}, s_{j,2}, \ldots, s_{j,k_j},用空格分隔。如果 k_j = 0,仅 该行给出了 k_j 。
输出
在一行中打印选择最佳分组时受损计算机的最少数量。
示例输入 1
3 3 2 1 2 2 2 3 1 1
示例输出 1
1
示例输入 2
4 4 0 2 1 2 2 3 4 4 1 2 3 4
示例输出 2
0
示例输入 3
8 10 3 1 2 3 2 3 4 4 2 4 6 8 1 5 0 3 5 6 7 2 1 8 5 1 3 5 7 8 2 6 7 4 1 2 7 8
示例输出 3
1
示例输入 4
15 25 0 1 1 1 15 2 1 2 2 2 3 3 1 3 5 3 4 5 6 4 1 4 7 10 4 2 5 8 11 5 3 6 9 12 15 5 1 5 9 13 14 6 2 4 6 8 10 12 6 3 5 7 9 11 13 7 1 2 3 4 5 6 7 7 9 10 11 12 13 14 15 8 1 3 5 7 9 11 13 15 8 2 4 6 8 10 12 14 15 9 1 2 4 5 7 8 10 11 13 10 3 4 5 6 7 8 9 10 11 12 11 1 2 3 5 6 7 9 10 11 13 14 12 1 2 3 4 6 7 8 9 11 12 13 14 13 1 2 3 4 5 7 8 9 10 11 13 14 15 14 1 2 3 4 5 6 8 9 10 11 12 13 14 15 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3 13 14 15
示例输出 4
2
示例输入 5
1 1 0
示例输出 5
0