博弈问题之SG函数博弈小结
SG函数：
给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移 动者判负。事实上，这个游戏可以认为是所有Impartial Combinatorial Games的抽象模型。也就是说，任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下 面我们就在有向无环图的顶点上定义Sprague-Garundy函数。首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
在我的理解中，sg函数就是一个对有向无环图dfs的过程，在处理nim博弈时，多个石堆可以看成多个sg函数值的异或。
例题：
POJ2311 Cutting Game
典型的sg博弈，找后继状态。题意是给出一个n*m的纸片，每次剪成两部分，谁先剪到1*1就胜利。这就是一个找后继的题目，每次剪成的两部分就是前一状态的后继，只要将两个部分的sg值异或起来就是前一状态的sg值。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<cmath>#include<set>#include<vector>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define FOR(a,b,i) for(i=a;i<=b;++i)#define For(a,b,i) for(i=a;i<b;++i)#define N 1000000007using namespace std;inline void RD(int &ret){ char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); }}inline void OT(int a){ if(a>=10) { OT(a/10); } putchar(a%10+'0');}int n,v[1001][1001],vis[1001];int dfs(int x){ int i; FOR(1,n,i) { vis[x]=1; if(v[i][x]&&!vis[i]) { if(!dfs(i)) { vis[x]=0; return i; } } vis[x]=0; } return 0;}int main(){ int m,i,a,b; while(scanf("%d%d",&n,&m)!=EOF) { mem(v,0); mem(vis,0); FOR(1,n-1,i) { RD(a); RD(b); v[a][b]=v[b][a]=1; } i=dfs(m); if(i!=0) { printf("First player wins flying to airport %d\n",i); } else { printf("First player loses\n"); } } return 0;}