UVa1671/LA4358 History of Languages题目链接题意分析AC 代码题目链接本题是2008年icpc亚洲区域赛杭州赛区的H题题意输入两个DFA判断是否等价。第一行为字母表的大小T2≤T≤26然后是两个DFA的描述。每个DFA的第一行为状态数nn≤2000以下n行每行描述一个状态格式为F,X0, X1,…, XT-1其中F表示是否为终态F1表示是0表示否。-1≤XiN表示该状态读入i后转移到的状态其中-1表示该转移不存在。两个DFA的起始状态均为0。分析《入门经典》自动机的例题题解如下本题的做法不止一种这里选择一个概念上最简单的做法把“a和b等价”转化为“a的补和b不相交且b的补和a不相交”。如何求DFA的补也就是把接受的串变成不接受的串不接受的串变成接受的串。由此可以想到只需把终态和非终态互换即可。如何判断两个DFA不相交可试着找一个同时被两个DFA接受的串如果找不到则说明两个DFA不相交。如何找这个串构造一个新的DFA它的每个状态都可以写成(q1, q2)其中q1和q2分别是两个DFA中的状态当且仅当q1和q2分别是两个DFA的终态时(q1, q2)是新DFA的终态。这样问题就转化为了找一个被新DFA接受的串。这只需要用经典的图遍历DFS或BFS即可时间复杂度为O ( n 2 ) O(n^2)O(n2)。本题还有一个细节即对于“该转移不存在”的处理。虽然可以直接处理但更经典的方法是加一个“所有转移都指向自己”的“孤岛状态”把所有不存在的转移都改成转移到孤岛。这样一来所有转移都是存在的程序比较好写。对于“该转移不存在”的处理一定要按照题解说的“孤岛状态”方式去做不要头铁直接处理。AC 代码#includeiostream#includecstringusingnamespacestd;#defineT26#defineN2001boolvis[N][N];intt,kase0;structdfa{ints[N][T],f[N];intn;voidread(){f[0]0;cinn;for(inti1;in;i){cinf[i];for(intj0,u;jt;j)cinu,s[i][j]u;}}}a,b;booldfs(intx1,inty1){vis[x][y]true;if(a.f[x]^b.f[y])returntrue;for(inti0;it;i){intx1a.s[x][i],y1b.s[y][i];if(!vis[x1][y1]dfs(x1,y1))returntrue;}returnfalse;}voidsolve(){a.read();b.read();memset(vis,0,sizeof(vis));coutCase #kase: (dfs()?No:Yes)endl;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cintt)solve();return0;}