分数: 300 点
问题陈述
有 N 人数 1 to N。他们每个人要么是一个 诚实 证词始终正确的人或 不友善 其证词可能正确或错误的人。
人 i 给出 A_i 证词。的 j- 个人证词 i 由两个整数表示 x_{ij} 和 y_{ij}。如果 y_{ij} = 1,证词称 Person x_{ij} 是诚实的;如果 y_{ij} = 0,它说人 x_{ij} 很不友善。
其中有多少诚实人 N 最多人?
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 15
- 0 \leq A_i \leq N - 1
- 1 \leq x_{ij} \leq N
- x_{ij} \neq i
- x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)
- y_{ij} = 0, 1
输入
输入由标准输入按以下格式给出:
N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}
输出
打印出诚实人的最大可能数量 N 人。
示例输入 1
3 1 2 1 1 1 1 1 2 0
示例输出 1
2
如果人 1 和人 2 诚实、做人 3 不厚道,我们有两个诚实人,没有矛盾,这是最大可能的诚实人数量。
示例输入 2
3 2 2 1 3 0 2 3 1 1 0 2 1 1 2 0
示例输出 2
0
假设其中一个或多个是诚实的,就会立即导致矛盾。
示例输入 3
2 1 2 0 1 1 0
示例输出 3
1