# [题解] 2023 CCPC 华为云计算挑战赛 博弈,启动! [BFS]
# 题目大意
给定一个有向二分图,分为 部分和 部分,有一个棋子位于图上任意一节点。当棋子在 部分时,玩家 沿节点出边操作棋子;当棋子在 部分时,玩家 沿出边操作棋子。循环往复该过程,直至棋子到达的节点没有出边。 的目标是让棋子在图上每个节点经过无穷次, 的目标与之相反。两人均采取最优策略,问 是否有必胜策略。
# 题解
先来剖析一下题目的意思, 获胜的条件是:从任意一点出发,棋子能经过且能无穷次经过每一个节点。
我们将每个节点分开考虑,对于每个节点,从任意节点出发,无论 如何操作, 都能合适地操作,使棋子一定能到达。若所有节点都一定能到达,那么显然可以无穷次到达任意节点。
假设当前棋子在 部分的节点 上,那么:只要是 连出的点的可到达点,也一定是 的可到达点。
假设当前棋子在 部分的节点 上,那么:只有是 连出所有的点均可到达的点,才能是 的可到达点。
对于每个节点,从 出发,我们要传递上述的可到达关系。像最短路那样,我们倒序跑 即可。
# 代码
#include<cstdio> | |
#include<vector> | |
#include<queue> | |
#include<bitset> | |
const int MAXN=601; | |
int T,N,M; | |
std::bitset<MAXN> to[MAXN]; | |
std::vector<int> ito[MAXN]; | |
std::bitset<MAXN> reach; | |
std::queue<int> q; | |
void bfs(int S){ | |
reach.reset(); | |
while(q.size()) | |
q.pop(); | |
q.push(S); | |
reach[S]=1; | |
while(q.size()){ | |
int x=q.front(); | |
q.pop(); | |
for(int tt:ito[x])if(!reach[tt]){ | |
if(tt>N){ | |
if((to[tt]&reach)==to[tt]){ | |
reach[tt]=1; | |
q.push(tt); | |
} | |
} | |
else{ | |
reach[tt]=1; | |
q.push(tt); | |
} | |
} | |
} | |
} | |
inline void add(const int &x,const int &y){ | |
to[x][y]=1; | |
ito[y].push_back(x); | |
} | |
int main(){ | |
scanf("%d",&T); | |
while(T--){ | |
scanf("%d%d",&N,&M); | |
for(int i=1;i<=N+M;++i) | |
to[i].reset(),ito[i].clear(); | |
for(int x=1;x<=N;++x){ | |
int n,y; | |
scanf("%d",&n); | |
for(int i=1;i<=n;++i){ | |
scanf("%d",&y); | |
add(x,N+y+1); | |
} | |
} | |
for(int x=1;x<=M;++x){ | |
int n,y; | |
scanf("%d",&n); | |
for(int i=1;i<=n;++i){ | |
scanf("%d",&y); | |
add(N+x,y+1); | |
} | |
} | |
for(int i=1;i<=N+M;++i){ | |
bfs(i); | |
if(reach.count()!=N+M){ | |
printf("No\n"); | |
goto Cont; | |
} | |
} | |
printf("Yes\n"); | |
Cont:; | |
} | |
} |