HDU1524(博弈--有向无环图SG函数)

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1524

题意:在一个有向无环图上有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 <string.h>
#include <stdio.h>

using namespace std;
const int N = 2005;

int head[N];
int n,m,cnt;

struct Edge
{
    int to;
    int next;
};

Edge edge[N*N];
int SG[N];

void Init()
{
    cnt = 0;
    memset(SG,-1,sizeof(SG));
    memset(head,-1,sizeof(head));
}

void add(int u,int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

int mex(int x)
{
    if(SG[x] != -1) return SG[x];
    bool vis[N];
    memset(vis,0,sizeof(vis));
    for(int i=head[x];~i;i=edge[i].next)
    {
        int v = edge[i].to;
        SG[v] = mex(v);
        vis[SG[v]] = 1;
    }
    for(int i=0;;i++)
    if(!vis[i]) return i;
}

int main()
{
    while(~scanf("%d",&n))
    {
        Init();
        for(int i=0;i<n;i++)
        {
            scanf("%d",&m);
            while(m--)
            {
                int u;
                scanf("%d",&u);
                add(i,u);
            }
        }
        int k;
        while(~scanf("%d",&k))
        {
            if(k == 0) break;
            int ans = 0;
            while(k--)
            {
                int x;
                scanf("%d",&x);
                ans ^= mex(x);
            }
            if(ans) puts("WIN");
            else    puts("LOSE");
        }
    }
    return 0;
}