← 返回题目列表

AtCoder · awc0099_e

E. 群体划分与病毒感染

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

分数: 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