poj 3710——Christmas Game

喜欢ヅ旅行 2022-07-15 08:56 134阅读 0赞

题意：

给定多个无向有环图，两个人在树上博弈，问博弈结果。

思路：

如果没有环，则是一个标准的树上博弈，那么满足  
1. 叶子节点的sg为0  
2. 中间节点的sg为所有儿子节点的sg+1的异或和

存在环的话，可以缩点，偶数是0，奇数为1，具体证明看《[组合游戏略述——浅谈SG游戏的若干拓展及变形][SG]》

#include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <vector>
    using namespace std;
    
    const int N=1005;
    bool vis[N];
    int ve[N],s[N],w[N],top;
    int to[N],next[N],head[N],cnt;
    void addedge(int u,int v){
         to[++cnt]=v;next[cnt]=head[u];head[u]=cnt;
         to[++cnt]=u;next[cnt]=head[v];head[v]=cnt;
    }
    int dfs(int u){
        vis[u]=1;
        int ans=0;
        s[++top]=u;
        int tt,v;
        for (int i=head[u];i;i=next[i]){
             if(!ve[i]) {
                ve[i]=1;ve[i^1]=1;
                v=to[i];
                if(!vis[v]) tt=dfs(v)+1;
                else{
                     int q=s[top--];
                     while(q!=v) w[q]=1 , q=s[top--];
                     ++top;
                     return 1;
                }
                if(w[v]) ans^=(tt%2);
                else ans^=tt;
             }
        }
        return ans;
    }
    void init(int n){
        //for (int i=0;i<=n;i++) g[i].clear();
        memset(head,0,sizeof(head));
        memset(next,-1,sizeof(next));
        memset(vis,0,sizeof(vis));
        memset(ve,0,sizeof(ve));
        memset(w,0,sizeof(w));
        top=0;cnt=1;
    }
    int main(int argc, char const *argv[])
    {
        int T,n,m;
        while (~scanf("%d",&T)){
        int ans=0;
        while (T--){
            scanf("%d%d",&n,&m);
            init(n);
            for (int i=0;i<m;i++){
                int u,v;
                scanf("%d%d",&u,&v);
                addedge(u,v);
            }
            ans^=dfs(1);
        }
        if (ans) puts("Sally");
        else puts("Harry");
        }
        return 0;
    }

[SG]: http://wenku.baidu.com/link?url=xj2hLP3hRl1dEx6Ofyupc0nYgACjAis7jtCM-8MrMWQfws9JhHPVfyQBRo4ubLL18fv1atRzwX__vtoSXykz80I79H5zubDxvEcEc9fGB1G