POJ 2702 - Can a Complicated Program Go Wrong?

http://poj.org/problem?id=2702

概要

finite state machine (FSM) としてプログラムが与えられる。 同様に FSM として仕様が与えられる。 この仕様の FSM のノードには trap state が存在し、プログラムが生成する文字列によって遷移したときに trap state のノードに遷移しうるかどうか答える。

制約

解法

プログラムのノードと仕様のノードのペアで BFS して、仕様側で trap state に到達しうるかどうか調べる。

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 #include <map>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 typedef vector<multimap<char,int> > graph;
 9 typedef multimap<char,int>::const_iterator Iterator;
10 
11 pair<int,graph> read()
12 {
13   int S, E, I;
14   scanf("%d %d %d", &S, &E, &I);
15   --I;
16   graph g(S);
17   for (int i = 0; i < E; i++) {
18     int u, v;
19     char c;
20     scanf("%d %c %d", &u, &c, &v);
21     --u;  --v;
22     g[u].insert(make_pair(c, v));
23   }
24   return make_pair(I, g);
25 }
26 
27 bool solve(int prog_start, const graph& prog, int req_start, const graph& req)
28 {
29   vector<vector<int> > visited(prog.size(), vector<int>(req.size(), false));
30   visited[prog_start][req_start] = true;
31   queue<pair<int,int> > q;
32   q.push(make_pair(prog_start, req_start));
33   while (!q.empty()) {
34     const int i = q.front().first;
35     const int j = q.front().second;
36     q.pop();
37 
38     for (multimap<char,int>::const_iterator it = prog[i].begin(); it != prog[i].end(); ++it) {
39       const int k = it->second;
40       pair<Iterator, Iterator> r = req[j].equal_range(it->first);
41       if (r.first == r.second) {
42         // nothing in common
43         if (!visited[k][j]) {
44           visited[k][j] = true;
45           q.push(make_pair(k, j));
46         }
47       } else {
48         while (r.first != r.second) {
49           const int l = r.first->second;
50           if (l < 0) {
51             return false;
52           }
53           if (!visited[k][l]) {
54             visited[k][l] = true;
55             q.push(make_pair(k, l));
56           }
57           ++r.first;
58         }
59       }
60     }
61   }
62   return true;
63 }
64 
65 int main()
66 {
67   int T;
68   scanf("%d", &T);
69   while (T-- > 0) {
70     const pair<int,graph> prog = read();
71     const pair<int,graph> req = read();
72     puts(solve(prog.first, prog.second, req.first, req.second) ? "satisfied" : "violated");
73   }
74   return 0;
75 }
poj/2702.cc