题目大意:给你一个有向图, Bob 和 Alice 在做游戏,每轮他们走一步,当Bob 和 Alice在同一个点或者 Bob无路可走,Bob输,否则Alice输。
思路:因为在Bob赢的时候存在有环的情况, 但是在Bob输的时候的状态是明确的,我们利用Bob输的状态进行必胜比败态推演,
f[ i ][ j ][ k ] 表示Alice在i ,Bob在j 且轮到k走 Bob是必输还是必胜。
#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define pii pair<int, int> #define y1 skldjfskldjg #define y2 skldfjsklejg using namespace std; const int N = 100 + 7; const int M = 1e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 +7; int n, m, B, A, deg[N], num[N][N][2]; vector<int> edge[N], redge[N]; int f[N][N][2], vis[N][N][2]; struct node { node(int x, int y, int d) { this->x = x; this->y = y; this->d = d; } int x, y, d; }; void init() { for(int i = 0; i < N; i++) { edge[i].clear(); redge[i].clear(); } memset(deg, 0, sizeof(deg)); memset(vis, 0, sizeof(vis)); memset(num, 0, sizeof(num)); for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) f[i][j][0] = f[i][j][1] = 1; } void bfs() { queue<node> que; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { for(int k = 0; k < 2; k++) { if(i == j) { f[i][j][k] = 0; que.push(node(i, j, k)); vis[i][j][k] = 1; } else if(k == 1) { if(!edge[j].size()) { f[i][j][k] = 0; que.push(node(i, j, k)); vis[i][j][k] = 1; } } } } } while(!que.empty()) { node cur = que.front(); que.pop(); if(!cur.d) { for(int i = 0; i < redge[cur.y].size(); i++) { int nxy = redge[cur.y][i]; if(vis[cur.x][nxy][1]) continue; num[cur.x][nxy][1]++; if(num[cur.x][nxy][1] == deg[nxy]) { f[cur.x][nxy][1] = 0; vis[cur.x][nxy][1] = 1; que.push(node(cur.x, nxy, 1)); } } } else { for(int i = 0; i < redge[cur.x].size(); i++) { int nxx = redge[cur.x][i]; if(vis[nxx][cur.y][0]) continue; f[nxx][cur.y][0] = 0; vis[nxx][cur.y][0] = 1; que.push(node(nxx, cur.y, 0)); } } } } int main() { int T; scanf("%d", &T); for(int cas = 1; cas <= T; cas++) { init(); scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); edge[u].push_back(v); redge[v].push_back(u); deg[u]++; } scanf("%d%d", &B, &A); bfs(); printf("Case #%d: ", cas); printf("%s\n", f[A][B][1] ? "Yes" : "No"); } return 0; } /* */