#P1846. [HDOJ]2471 History of Languages

    ID: 868 传统题 1000ms 512MiB 尝试: 5 已通过: 4 难度: 4 上传者: 标签>CF1600普及+/提高-状态扩展图广度优先搜索状态编码状态去重

[HDOJ]2471 History of Languages

题目描述

给定两个确定性有限状态自动机(DFA)A,BA,B,判断 AA 和 BB 是否等价(即对于任意输入串,输出都一致)。

输入格式

输入有若干组数据,对于每一组输入数据:

第一行一个正整数 mm 表示字符集大小。

接下来描述 AA 和 BB,对于每一个 DFA:

第一行一个整数 nn 表示状态数。

接下来 nn 行,第 i+1i+1 行有 m+1m+1 个数 Fi,xi0,xi1,⋯ ,xim−1F_i,x_{i0},x_{i1},\cdots,x_{im-1},FiF_i 表示状态 ii 是否为终态,若 Fi=1F_i=1 表示状态 ii 是终态,否则不是;xicx_{ic} 表示状态 ii 通过字符 cc 转移到状态 xicx_{ic},若 xic=−1x_{ic}=-1 则表示无此转移边。

输出格式

对第 ii 组数据,输出单独一行 Case #i: Yes 或者 Case #i: No 表示第 ii 组数据中两个 DFA 是否等价。

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

Case #1: No
Case #2: Yes

数据规模与约定

1≤n≤20001\le n \le 2000,2≤m≤262\le m\le 26。