题目链接

题目大意

题目给定一个无向图，节点上放置有机器人，要求每一个回合机器人都要往相邻的节点走一步，问是否存在有一个节点，使得所有机器人在某一步中能够在此节点相会

思路分析

对于一个无向图而言，如果我们能在第$k$到达节点$n$，那么我们可以在他和相邻节点来回穿梭，即$k+2,k+4,k+6,...$这些时刻我们都可以到达这个节点。也就是说，在这道题中，我们在意的其实不是走多少步，而是步长的奇偶性。

需要注意的是，有些节点不管是奇数还是偶数都能到达。

因此，对于每一个机器人，我们只需要用BFS探索它对于每一个节点，奇数步和偶数步的到达情况，最后统计是否有节点满足对于所有机器人都能奇数步到达或者偶数步到达，即可。

这里我用了一个简单的位运算的技巧，1为奇数到达，2为偶数到达，3为两者都可，那么我们只需要把所有机器人到目标点的方法按位与即可。

TIPS：tobot的序号不一定是从1-n，有可能是0，也有可能超过n。

#define inf 0x3f3f3f3f #define ll long long #define vec vector<int> #define P pair<int,int> #define MAX 105 int T, n, k, u, v, m, a[MAX], vis[MAX], d[MAX][MAX], exi[MAX]; vec G[MAX]; int step(int k) {//从k的步数推出到相邻节点的步数 if (vis[k] == 1)return 2; else if (vis[k] == 2) return 1; else return 3; } void bfs(int k) { //0表示未访问，1表示奇数步，2表示偶数步，3表示都可 memset(vis, 0, sizeof(vis)); memset(exi, 0, sizeof(exi)); vis[k] = 2; queue<int> q; q.push(k); exi[k] = 1; while (!q.empty()) { int u = q.front(), s = step(u); q.pop(); exi[u] = 0; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (!vis[v]) { vis[v] = s; q.push(v); } else if (s != vis[v]) {//已经访问过了，但是有另一种走法 vis[v] = 3; if (!exi[v]) q.push(v), exi[v] = 1;//不在队列中则加入 } } } for (int i = 0; i < MAX; i++)d[k][i] = vis[i]; } int main() { scanf("%d", &T); while (T--) { scanf("%d %d", &n, &k); for (int i = 0; i < MAX; i++)G[i].clear(); for (int i = 1; i <= n; i++) { scanf("%d %d", &u, &m); for (int i = 0; i < m; i++) { scanf("%d", &v); G[u].push_back(v); } } memset(d, 0, sizeof(d)); for (int i = 0; i < k; i++) { scanf("%d", &a[i]); bfs(a[i]); } int sign = 0; for (int i = 0; i < MAX; i++) { //检查是否能都到这个节点 int res = d[a[0]][i]; for (int j = 1; j < k && res; j++) { res &= d[a[j]][i]; } if (res) { sign = 1; break; } } if (sign)cout << "YES" << endl; else cout << "NO" << endl; } }