POJ2425（树形，无向无环图博弈）

45 阅读 0 评论 30 点赞

我是靠谱客的博主标致草莓，最近开发中收集的这篇文章主要介绍POJ2425（树形，无向无环图博弈），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：题目链接

这道题目的意思是说两人挪棋子，棋子放在棋盘上，一个人挪动的时候可以移动到链接到的下一个点。当一个人不能挪动棋子的时候就输了。问先手是赢还是输？

如果光看一个石子的话，这就是sg函数的定义。然后对整个图处理一下每个点的sg值。对这M个点怎么处理，这么想吧。假设其中一个点为i，其sg值为sg[i] = a (a != 0)
那可以发现，i可以走向[0, a-1]的任意sg值，这相当与什么？相当与这里有一堆石子，共a个。M个点就是M堆石子，每堆石子的个数就是这个点的sg值。好吧Nim博弈出来了。

代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
int mp[1001][1001];
int SG[1001];
int N;

int DFS(int n)
{
    int i;
    if(SG[n]!=-1)
        return SG[n];
    bool next[1001];
    memset(next, 0, sizeof(next));
    for(i = 0; i < N; ++i)
    {
        if(mp[n][i] != -1)
            next[DFS(i)] = 1;
    }
    i = 0;
    while(next[i])
        i++;
    return SG[i] = i;
}
int main()
{
    int i, j, k, t;
    int X;
    int tp, ans;
    while(scanf("%d", &N)！=EOF)
    {
        memset(mp, -1, sizeof(mp));
        memset(SG, -1, sizeof(SG));
        for(i = 0; i < N; ++i)
        {
            scanf("%d", &k);
            if(k==0)
                SG[i] = 0;
            for(j =0 ; j < k; ++j)
            {
                scanf("%d", &t);
                mp[i][t] = 1;
            }
        }
        while(scanf("%d", &X))
        {
            if(X==0)
                break;
            ans = 0;
            for(i = 0; i < X; ++i)
            {
                scanf("%d", &tp);
                ans = ans ^ DFS(tp);
            }
            if(ans != 0)
                printf("WINn");
            else
                printf("LOSEn");
        }
    }
    return 0;
}

不过我的EOF不知道为什么貌似起不了作用，一直TLE，下面的这个A了，不懂EOF了，路过的大神给讲讲啊

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;

int map[1010][1010];
int SG[1010];
int N;

int DFS(int n)
{
    int i;
    if(SG[n]!=-1) return SG[n];
    bool used[1010];
    memset(used,0,sizeof(used));
    for(i=0; i<N; i++)
    {
        if(map[n][i] != -1)
            used[DFS(i)]=true;
    }
    i=0;
    while(used[i]) i++;
    return SG[n]=i;
}


int main()
{
    int i,j,k,t;
    int X;
    int tp,ans;
    while(scanf("%d",&N) != EOF)
    {
        memset(map,255,sizeof(map));
        memset(SG,255,sizeof(SG));
        for(i=0; i<N; i++)
        {
            scanf("%d",&k);
            if(k == 0)
            {
                SG[i] = 0;
            }
            for(j=0; j<k; j++)
            {
                scanf("%d",&t);
                map[i][t] = 1;
            }
        }

        while(scanf("%d",&X) != EOF)
        {
            if(X == 0) break;
            ans = 0;
            for(i=0; i<X; i++)
            {
                scanf("%d",&tp);
                ans = ans ^DFS(tp);
            }
            if(ans != 0)
                printf("WINn");
            else
                printf("LOSEn");
        }
    }
    return 0;
}

努力努力...