#P1194. [HNOI2006]潘多拉的盒子

    ID: 202 传统题 1000ms 256MiB 尝试: 699 已通过: 274 难度: 6 上传者: 标签>CF2100提高状态扩展图广度优先搜索普通并查集缩点Kahn 算法DAG 动态规划

[HNOI2006]潘多拉的盒子

[HNOI2006] 潘多拉的宝盒

题目描述

输入格式

输出格式

输出一行一个数tt,表示最长升级序列的长度。

样例 #1

样例输入 #1

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

样例输出 #1

3

样例 #2

样例输入 #2

3
1  1
0
0  0
3  1
0
0  1
2  0
1  2
9  1
0
0  1
2  3
4  5
6  7
8  0
1  2
3  4
5  6
7  8

样例输出 #2

3

提示

图片题面文字补充

一个咒语机是确定性二进制自动机,由编号 00 到 n−1n-1 的元件组成,初始处于元件0,信号为空串。若当前信号为 SS、所在元件为 ii,下一时刻可以选择追加0并移动到 pi,0p_{i,0},或追加1并移动到 pi,1p_{i,1}。有些元件是输出元件;信号到达输出元件时可以输出,得到一个咒语源。

若咒语机 ii 能产生的每个咒语源也都能被咒语机 jj 产生,则称 jj 是 ii 的升级,即语言包含关系。并未要求真包含:行为相同的两台机器可以互相升级。升级序列中的机器编号必须两两不同;求序列的最大长度。

输入第一行正整数 SS,1≤S≤501\le S\le50,表示机器数。随后按编号0到S-1描述每台机器:第一行两个正整数 n,mn,m,1≤m≤n≤501\le m\le n\le50;第二行给出m个输出元件编号(0到n-1)。再有n行,第i行(i从0起)为 pi,0,pi,1p_{i,0},p_{i,1},均在0到n-1之间。输出最长升级序列长度。