# [题解] 2023 CCPC 华为云计算挑战赛 博弈,启动! [BFS]

# 题目大意

给定一个有向二分图,分为GG 部分和YY 部分,有一个棋子位于图上任意一节点。当棋子在GG 部分时,玩家GGGG 沿节点出边操作棋子;当棋子在YY 部分时,玩家YYYY 沿出边操作棋子。循环往复该过程,直至棋子到达的节点没有出边。GGGG 的目标是让棋子在图上每个节点经过无穷次,YYYY 的目标与之相反。两人均采取最优策略,问GGGG 是否有必胜策略。

# 题解

先来剖析一下题目的意思,GGGG 获胜的条件是:从任意一点出发,棋子能经过且能无穷次经过每一个节点。
我们将每个节点分开考虑,对于每个节点vv,从任意节点出发,无论YYYY 如何操作,GGGG 都能合适地操作,使棋子一定能到达vv。若所有节点都一定能到达vv,那么显然可以无穷次到达任意节点。
假设当前棋子在GG 部分的节点gg 上,那么:只要是gg 连出的点的可到达点,也一定是gg 的可到达点。
假设当前棋子在YY 部分的节点yy 上,那么:只有是yy 连出所有的点均可到达的点,才能是yy 的可到达点。
对于每个节点vv,从vv 出发,我们要传递上述的可到达关系。像最短路那样,我们倒序跑bfsbfs 即可。

# 代码

#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:;
    }
}
更新于 阅读次数