写一些题解，把网络赛时候写的题记录下，免得以后找不到代码了～题目链接： hdu5487

Difference of Languages

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 376 Accepted Submission(s): 86

Problem Description

A regular language can be represented as a deterministic finite automaton (DFA). A DFA contains a finite set of states Q and a finite set of input symbols called the alphabet Σ. Initially, the DFA is positioned at the start state q0∈Q. Given the transition function δ(q,a) and an input symbol a, the DFA transit to state δ(q,a) if its current state is q. Let w=a1a2…an be a string over the alphabet Σ. According to the above definition, the DFA transits through the following sequence of states.

q0,q1=δ(q0,a1),q2=δ(q1,a2),…,qn=δ(qn−1,an)

The DFA also contains a set of accept states F⊆Q. If the last state qn is an accept state, we say that the DFA accepts the string w. The set of accepted strings is referred as the language that the DFA represents. You are given two DFAs, and the languages that they represent may be different. You want to find the difference between the two languages. Specifically, you are trying to find a string that is accepted by one DFA but not accepted by the other DFA. As there could be multiple such strings, you only want the shortest one. If there are still multiple such strings, you would like the smallest one in lexicographical order.

Input

The first line of input contains a number T indicating the number of test cases (T≤200). Each test case contains the description of two DFAs. For the first DFA, the first line contains three integers N, M, and K, indicating the number of states, the number of rules describing the transition function, and the number of accept states (1≤K≤N≤1000,0≤M≤26N). The states are numbered from 0 to N–1. The start state is always 0. The second line contains K integers representing the accept states. All these numbers are distinct. Each of the next M lines consists of two states p and q, and an input symbol a, which means that the DFA transits from p to q when it receives the symbol a. You may assume that the alphabet in consideration consists of the 26 lowercase letters (a-z). It is guaranteed that, given p and a, the next state q is unique. The description of the second DFA follows the same format as the above.

Output

For each test case, output a single line consisting of “Case #X: Y”. X is the test case number starting from 1. Y is the shortest string that is accepted by one DFA but not accepted by the other DFA. If no such string exists, output the digit “0” instead. Note that an empty string is also considered a string.

Sample Input

2 3 3 1 2 0 1 a 1 2 b 2 0 c 4 4 1 3 0 1 a 1 2 b 2 3 c 3 0 a 3 3 1 2 0 1 a 1 2 b 2 0 c 3 4 1 2 0 1 a 1 2 b 1 2 c 2 0 c

Sample Output

Case #1: ab Case #2: ac

Source

2015 ACM/ICPC Asia Regional Hefei Online

题意大致就是两个自动机， 要求出一个最短的字符串，可以被其中一个自动机接受，不能被另外一个接受。 直接暴力，BFS转移就可。 BFS出来第一个就是最短的了，而且字典序是最小的。 注意转移的一些细节就好。

/* ***
Author :kuangbin
Created Time :2015/9/27 15:29:44
File Name :F:\ACM\2015ACM\2015ÍøÂçÈü\2015ºÏ·Ê\1004.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
struct Trie {
int next[2010][26];
bool end[2010];
int n;
void init(int _n) {
memset(next,-1,sizeof(next));
for(int i = 0;i < 26;i++)
next[_n][i] = _n;
n = _n;
memset(end,false,sizeof(end));
}
void add(int u,int v,char ch) {
next[u][ch-‘a’] = v;
}
}tree1,tree2;

struct Node {
int s1,s2;
Node(int _s1=0,int _s2=0) {
s1 = _s1;
s2 = _s2;
}
Node next(int i) {
Node ret;
ret.s1 = tree1.next[s1][i];
ret.s2 = tree2.next[s2][i];
if(ret.s1 == -1)ret.s1 = tree1.n;
if(ret.s2 == -1)ret.s2 = tree2.n;
return ret;
}
};
int dp[1020][1020];
pair<int,int> pres[1020][1020];
int prech[1020][1020];
char str[1020];

bool bfs() {
queueq;
memset(dp,-1,sizeof(dp));
q.push(Node(0,0));
dp[0][0] = 0;
while(!q.empty()) {
Node now = q.front();
int s1 = now.s1;
int s2 = now.s2;
q.pop();
if ( (tree1.end[now.s1]^tree2.end[now.s2]) ) {
str[dp[s1][s2]] = 0;
int len = dp[s1][s2];
for(int i = 0;i < len;i++) {
str[len-1-i] = (prech[s1][s2]+’a’);
pair<int,int>tmp = pres[s1][s2];
s1 = tmp.first;
s2 = tmp.second;
}
return true;
}
for(int i = 0;i < 26;i++) {
if(!tree1.next[s1][i] && !tree2.next[s2][i])continue;
Node nn = now.next(i);
if(dp[nn.s1][nn.s2] != -1)continue;
dp[nn.s1][nn.s2] = dp[s1][s2]+1;
pres[nn.s1][nn.s2] = make_pair(s1,s2);
prech[nn.s1][nn.s2] = i;
q.push(nn);
}
}
return false;
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int iCase = 0;
scanf(“%d”,&T);
while(T–) {
iCase++;
int n,m,k;
scanf(“%d%d%d”,&n,&m,&k);
tree1.init(n);
int u,v;
while(k–) {
scanf(“%d”,&u);
tree1.end[u] = true;
}
char ss[10];
while(m–) {
scanf(“%d%d%s”,&u,&v,ss);
tree1.add(u,v,ss[0]);
}
scanf(“%d%d%d”,&n,&m,&k);
tree2.init(n);
while(k–){
scanf(“%d”,&u);
tree2.end[u] = true;
}
while(m–) {
scanf(“%d%d%s”,&u,&v,ss);
tree2.add(u,v,ss[0]);
}
if(bfs())printf(“Case #%d: %s\n”,iCase,str);
else printf(“Case #%d: 0\n”,iCase);
}
return 0;
}