題意：一個無向有環的圖，從 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; } View Code

?

轉載于:https://www.cnblogs.com/TreeDream/p/7082733.html

總結

以上是生活随笔為你收集整理的Gym - 101246D 博弈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。