hdu 1524 A Chess Game (SG)

hdu 1524 A Chess Game (SG)

題意:在一個有向無環圖上有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 
# include 
# include 
# include 
#include 
using namespace std;
vectorg[1010];
int sg[1010];

int GetSG(int x)
{
    int i;
    if(sg[x]!=-1)
        return sg[x];
    if(g[x].size()==0)
        return sg[x]=0;
    int vis[1010];//
    memset(vis,0,sizeof(vis));
    for(i=0; i