题意:在一个有向无环图上有n个顶点,每一个顶点都只有一个棋子,有两个人,每次根据这个图只能将任意一颗棋子移动一步
,如果到某一步玩家不能移动时,那么这个人就输.
分析:本题是最典型的有向无环图的博弈,利用dfs把所有顶点的SG值都计算出来,然后对每个棋子的SG值进行异或运算,如果
为0就是先手必败,否则就是先手必胜.
如果某个人移动到出度为0的顶点,那么他必败,在这里首先介绍一下什么是SG函数.
对于给定的有向无环图,定义图中每个顶点的Sprague-Grundy函数g如下：g(x) = mex{ g(y) | y是x的后继 }。
mex(x)表示最小的不属于这个集合的非负整数。例如：mex{0,1,2,4} = 3、mex{2,3,5} = 0、mex{ } = 0。
SG函数的性质:首先,所有终结点所对应的顶点，也就是出度为0的顶点，其SG值为0，因为它的后继集合是空集。然后对于一
个g(x) = 0的顶点x，它的所有后继y都满足g(y)!=0。对于一个g(x)!=0的顶点，必定存在一个后继y满足g(y)=0.
而求整个SG函数值的过程就是一个对有向无环图进行深搜过程.
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 2005, INF = 0x7fffffff; int head[maxn], sg[maxn]; int cnt = 0; struct node { int u, v, next; }Node[maxn*maxn]; void add(int u, int v) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].next = head[u]; head[u] = cnt++; } int mex(int u) { if(sg[u] != -1) return sg[u]; bool vis[maxn]; //这个标记数组要放在里面 和普通求sg一样 每个点都有自己的一个vis 因为普通sg是循环所以放在外面就可以 而这里是递归 所以要放在里面 mem(vis, 0); for(int i=head[u]; i!=-1; i=Node[i].next) { node e = Node[i]; sg[e.v] = mex(e.v); //去找后继状态 vis[sg[e.v]] = 1; } for(int i=0; ; i++) if(!vis[i]) return i;
return 0; } int main() { int n; while(cin>> n) { mem(sg, -1); mem(head, -1); cnt = 0; int k; for(int i=0; i<n; i++) { cin>> k; for(int j=0; j<k; j++) { int v; cin>> v; add(i, v); } } int m, res = 0; while(cin>> m && m) { int u; res = 0; for(int i=0; i<m; i++) { cin>> u; res ^= mex(u); } if(res) cout<< "WIN" <<endl; else cout<< "LOSE" <<endl; } } return 0; }
参考自：https://blog.csdn.net/acdreamers/article/details/16923157