2023 CCPC 华为云计算挑战赛 hdu7399 博弈，启动！（图上博弈/枚举+逆向有向图sg函数）

题目

给定t(t<=200)组样例，

每次给定一个n(n<=300)个左边的点m(m<=300)个右边的点的二分图，图无重边

所有边总量不超过5e5

初始时棋子可以被放置在任意一个点上，

若被放置在左边，则Alice先走；被放置在右边，则Bob先走

每次可以选择一个当前点有出边的点，走到那个点上，如果当前点没有出边，则游戏结束

Alice想访问所有点无数次，Bob想阻止Alice这么做，双方均采取最优策略

问Alice是否有必胜策略（Alice可以指定起点在哪里）

思路来源

heltion+蔡老师

题解

问题等价于，

只要Bob能找到一个点，使Alice不能无限次经过，则Bob胜，否则Alice胜

称这样的点为防御点，

n=300，所以考虑枚举防御点

对于枚举的防御点，先判断一下可达性，如果有点到不了防御点，则Alice全局必败

防御点是一个终态点，如果Alice不能到防御点，则Bob不能去指向防御点的点，以此类推…

已知终态不知起始态，其实与期望dp类似，启发我们建反图后从防御点拓扑排序
 

然后考虑类似拓扑排序的更新流程，实际就是sg函数的思想，

初始时，将防御点放入队列，

对二分图上的点，每个点计算一个dp值，

如果防御点位于左侧，则Alice到这个点就视为（在只考虑这个防御点时）获胜，置dp值为1

如果防御点位于右侧，则Bob到这个点就视为失败，置dp置为0

如果一个点的所有下游（反图的上游）都是对方的必胜点，则这个点是必败点

如果一个点的所有下游（反图的上游）存在对方的必败点，则这个点是必胜点

如果一个点确定了必胜/必败态，就将这个点放入队列，直至更新完所有点

跑完这一轮后，Alice必败&Bob必胜的起点需要被排除

此时，有一些点可能是没被更新过的，即拓扑排序中的环，

这些点的特性是：

1. 不存在下游是对方的必败点

2. 存在一部分下游点是对方的必胜点，

3. 另一部分下游是状态未确定的点

那如果Alice和Bob在这些点上玩的话，都只会走向状态未确定的点，使Alice永远走不到防御点

所以这些状态未确定的点，也需要被过滤排除

枚举完一个防御点就会过滤掉一些点，

枚举完所有点后，没被过滤掉的点，就是Alice的必胜起点，若不存在则Bob必胜

其实感觉是很典的拓扑图上sg问题

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=605;
int T,n,m,u,v,k,c,dp[N],deg[N],d[N];
bool no[N],can[N];
vector<int>e[N];
void add(int u,int v){e[v].pb(u);deg[u]++;
}
bool L(int x){return x<n;
}
bool sol(int s){memset(dp,-1,sizeof dp);for(int i=0;i<n+m;++i)can[i]=0,d[i]=deg[i];queue<int>q;q.push(s);dp[s]=L(s);//点s表示GG想走到这里YY不想走到这里，位于左侧GG赢，位于右侧YY输can[s]=1;while(!q.empty()){int u=q.front();q.pop();for(auto &v:e[u]){can[v]=1;--d[v];if(~dp[v])continue;if(dp[u]==0)dp[v]=1;if(dp[u]==1 && !d[v])dp[v]=0;if(~dp[v])q.push(v);}}for(int i=0;i<n+m;++i){if(!can[i])return 0;if(L(i) && dp[i]==0)no[i]=1;if(!L(i) && dp[i]==1)no[i]=1;if(dp[i]==-1)no[i]=1;}return 1;
}
bool solve(){for(int i=0;i<n+m;++i){if(!deg[i])return 0;}memset(no,0,sizeof no);for(int i=0;i<n+m;++i){if(!sol(i))return 0;}for(int i=0;i<n+m;++i){if(!no[i])return 1;}return 0;
}
int main(){scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=0;i<n+m;++i){e[i].clear();deg[i]=0;}for(int i=0;i<n;++i){scanf("%d",&k);for(int j=1;j<=k;++j){scanf("%d",&v);add(i,n+v);}}for(int i=0;i<m;++i){scanf("%d",&k);for(int j=1;j<=k;++j){scanf("%d",&v);add(n+i,v);}}puts(solve()?"Yes":"No");}return 0;
}