首页 > 代码库 > Gym - 101246D 博弈
Gym - 101246D 博弈
题意：一个无向有环的图，从 1 号结点起火，开始蔓延，两个绝顶聪明的人轮流走，谁不能走谁输，输出输的人；
分析：
当时知道是博弈，但是想当然的以为 1 号结点有一个奇数层，就必胜；其实不是这样的，当一个人往奇数层走的时候，来到分叉点，另一个会找一个偶数走。
于是，还是得用SG博弈，
1、将图转换为一个有向无环图；
2、SG函数，下一个状态是子节点；
#include <bits/stdc++.h>using namespace std;int n,m;const int maxn = 1000 + 5;vector<int> G[maxn];vector<int> new_G[maxn];int t[maxn];void bfs() { memset(t,-1,sizeof(t)); queue<int> Q; Q.push(1); t[1] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(t[v]!=-1) continue; t[v] = t[u] + 1; Q.push(v); } }}void re_build() { for(int i=1;i<=n;i++) { for(int j=0;j<G[i].size();j++) { int v = G[i][j]; if(t[v]==t[i]+1) new_G[i].push_back(v); } }}int SG[maxn];void dfs(int u) { if(new_G[u].size()==0) { SG[u] = 0; return ; } for(int i=0;i<new_G[u].size();i++) { int v = new_G[u][i]; dfs(v); } for(int i=0;;i++) { bool flag = false; for(int j=0;j<new_G[u].size();j++) { if(SG[new_G[u][j]]==i) { flag = true; break; } } if(flag ==false) { SG[u] = i; break; } }}int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } bfs(); re_build(); dfs(1); if(SG[1]==0) puts("Nikolay"); else puts("Vladimir"); return 0;}
Gym - 101246D 博弈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。