POJ 1227 - RoboContest

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

概要

頂点数 \(n\) の連結無向グラフとしてマップが与えられ、\(k\) 個のロボットをいずれかの頂点に置く (同じ頂点に複数のロボットを置ける)。

各ステップですべてのロボットが同時に隣接する頂点に移動する。 これを繰り返したとき、ある1つの頂点にすべてのロボットが同時に存在させることができるかどうかを答える。

制約

• \(1 \le n \le 100)
• \(1 \le k \le 100)

解法

ある頂点にいるロボットが最後に集合できるような頂点は、スタート地点から2歩ずつ進んで到達できるような頂点である。 だから、各頂点から2歩ずつ進む BFS をして、すべての頂点から到達可能な頂点が存在するかどうか調べればいい。

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 #include <map>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 struct renamer
 9 {
10   map<int,int> m;
11   int operator()(int n)
12   {
13     if (m.count(n)) {
14       return m[n];
15     } else {
16       int id = m.size();
17       m.insert(make_pair(n, id));
18       return id;
19     }
20   }
21 };
22 
23 void bfs(vector<int>& even, const vector<vector<int> >& g, int start)
24 {
25   queue<int> q;
26   q.push(start);
27   even[start] = true;
28   while (!q.empty()) {
29     const int n = q.front();
30     q.pop();
31     for (vector<int>::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
32       for (vector<int>::const_iterator jt = g[*it].begin(); jt != g[*it].end(); ++jt) {
33         if (!even[*jt]) {
34           even[*jt] = true;
35           q.push(*jt);
36         }
37       }
38     }
39   }
40 }
41 
42 bool ok(const vector<vector<int> >& even)
43 {
44   const int K = even.size(), N = even[0].size();
45   for (int i = 0; i < N; i++) {
46     for (int j = 0; j < K; j++) {
47       if (!even[j][i]) {
48         goto FAIL;
49       }
50     }
51     return true;
52 FAIL:
53     ;
54   }
55   return false;
56 }
57 
58 int main()
59 {
60   int T;
61   scanf("%d", &T);
62   while (T-- > 0) {
63     int N, K;
64     scanf("%d %d", &N, &K);
65     vector<vector<int> > g(N);
66     renamer r;
67     for (int i = 0; i < N; i++) {
68       int n, m;
69       scanf("%d %d", &n, &m);
70       const int u = r(n);
71       for (int j = 0; j < m; j++) {
72         int x;
73         scanf("%d", &x);
74         const int v = r(x);
75         g[u].push_back(v);
76         g[v].push_back(u);
77       }
78     }
79 
80     vector<vector<int> > even(K, vector<int>(N, 0));
81     for (int i = 0; i < K; i++) {
82       int n;
83       scanf("%d", &n);
84       bfs(even[i], g, r(n));
85     }
86     puts(ok(even) ? "YES" : "NO");
87   }
88   return 0;
89 }