HonestOrUnkind2

题目描述

有 $N$ 个人，编号为 $1$ 到 $N$。他们中的每个人要么是证词总是正确的诚实者，要么是证词可能正确也可能不正确的不诚实者。 第 $i$ 个人给出 $A_i$ 条证词。第 $i$ 个人的第 $j$ 条证词由两个整数 $x_{ij}$ 和 $y_{ij}$ 表示。如果 $y_{ij} = 1$，该证词表示第 $x_{ij}$ 个人是诚实的；如果 $y_{ij} = 0$，则表示第 $x_{ij}$ 个人是不诚实的。 在这 $N$ 个人中，最多有多少个诚实的人？

输入格式

输入按以下格式由标准输入给出： $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$ 个人中最多可能的诚实人数。

3
1
2 1
1
1 1
1
2 0

2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

0

2
1
2 0
1
1 0

1

提示

输入中的所有值均为整数。 $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$如果第 $1$ 个人和第 $2$ 个人是诚实的，第 $3$ 个人是不诚实的，那么我们有两位诚实的人且没有矛盾，这是最多可能的诚实人数。
假设其中一人或多人是诚实的会立即导致矛盾。

标签: AtCoder|abc147C

来源

AtCoder|abc147C