POJ 3710 Christmas Game#经典图SG博弈

（说实话对于Tarjan算法在搞图论的时候就没搞太懂，以后得找时间深入了解）

（以下有关无向图删边游戏的资料来自论文贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》）

首先，对于无向图的删边游戏有如下定理性质：

1.（Fushion Principle定理）我们可对无向图做如下改动：将图中的任意一个偶环缩成一个新点，任意一个奇环缩成一个新点加一个新边；所有连到原先环上的边全部改为与新点相连；这样的改动不影响图的SG值。

2.（1）对于长度为奇数的环，去掉其中任意一个边之后，剩下的两个链长度同奇偶，抑或之后的SG值不可能为奇数，所以它的SG值为1；

（2）对于长度为偶数的环，去掉其中任意一个边之后，剩下的两个链长度异奇偶，抑或之后的SG值不可能为0，所以它的SG值为0；

3.对于树的删边游戏，有如下定理：

叶子节点的SG值为0；中间节点的SG值为它的所有子节点的SG值+1后的异或和。

所以对于这道题，用连通图的Tarjan算法找出环，然后删环，变成简单树，再进行Nim计算即可。

AC代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

vector<int> edge[105]; //邻接表

int belong[105][105]; //存放边的数量

int low[105],dfn[105];

int s[105],top; //堆栈

bool instack[105];

bool vis[105]; //用于标记不需要的点

void tarjan(int u,int pre,int depth)

{

    low[u]=dfn[u]=depth;//depth是时间戳，即level

    s[top++]=u;

    instack[u]=true;

    for(int i=0;i<edge[u].size();i++)

    {

        int v=edge[u][i];

        if(v==pre&&belong[u][v]>1) //判断重边

        {

            if(belong[u][v]%2==0)//偶环

                vis[u]=true;

            continue;

        }

        if(!dfn[v])

        {

            tarjan(v,u,depth+1);

            low[u]=min(low[u],low[v]);

        }

        else if(v!=pre&&instack[v])

            low[u]=min(low[u],dfn[v]);

    }

    if(dfn[u]==low[u])

    {

        int cnt=1;

        top--;

        while(s[top]!=u)

        {

            vis[s[top--]]=true;

            cnt++;

        }

        if(cnt&&(cnt&1)) //若节点为奇数，则保留两个点加一条边

            vis[s[top+1]]=false;

    }

}

int getsg(int u,int pre)

{

    int res=0;

    for(int i=0;i<edge[u].size();i++)

    {

        int v=edge[u][i];

            res^=(getsg(v,u)+1);

        //叶子节点sg=0，其所有子节点的sg+1后进行异或

    }

    return res;

}

void init(int m)

{

    for(int i=1;i<=m;i++)

        edge[i].clear();

    memset(belong,0,sizeof(belong));

    memset(low,0,sizeof(low));

    memset(dfn,0,sizeof(dfn));

    memset(instack,0,sizeof(instack));

    memset(vis,0,sizeof(vis));

    top=0;

}

void add_edge(int u,int v)

{

    belong[u][v]++;

    belong[v][u]++;

    edge[u].push_back(v);

    edge[v].push_back(u);

}

int main()

{

    int n,m,k;

    while(~scanf("%d",&n))

    {

        int res=0;

        while(n--)

        {

            scanf("%d%d",&m,&k);

            init(m);

            while(k--)

            {

                int u,v;

                scanf("%d%d",&u,&v);

                add_edge(u,v);

            }

            tarjan(1,-1,1);

            res^=getsg(1,-1);

        }

        if(res)

            printf("Sally\n");

        else printf("Harry\n");

    }

    return 0;

}

巴特西

POJ 3710 Christmas Game#经典图SG博弈

最新文章

热门文章