POJ 2425 A Chess Game（SG函数的有向图博弈游戏）

题目链接：http://poj.org/problem?id=2425

题目大意：就是nim游戏的有向图形式，输入一个n,接下来n行表示0-n-1为起点的有向边，每行的第一个数表示与起点相连的终点个数，之后是各个终点。构建有向图完成。

接下来就要在有向图的顶点上放棋子。有一系列的询问，询问以m开头，表示有m个棋子，之后m个数是棋子所在的顶点编号。两人轮流沿着有向边移动棋子，最终不能移动棋子的输。m为0结束询问。

这题可以加深对sg函数的理解，先求出每个点的sg值，然后对给定的点的sg值异或就可以了。至于为什么，可以看看这篇博客中的有向图和sg函数理解。http://www.cnblogs.com/hsqdboke/archive/2012/04/21/2461034.html

不知道为什么用邻接表就WA了，不过数据量不大，用矩阵不碍事。

注意点：1、记忆化搜索否则超时。

               2、vis数组并不是全局共享的，而是一个点有一个vis数组，是局部变量。

#include<vector>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
//vector<int> mp[1005];
int mp[1005][1005];
int n, m;
int g[1005];
int dfs(int k) {
    if(g[k] != -1) {
        return g[k];
    }
    bool vis[1005] = {0};
//    for (int i = 0; i < mp[k].size(); i ++) {
//        g[i] = dfs(mp[k][i]);
//        vis[g[i]] = 1;
//    }
    for (int i = 0; i < n; i ++) {
        if(mp[k][i]) {
            g[i] = dfs(i); // 记忆化搜索
            vis[g[i]] = 1;
        }
    }
    for (int i = 0; i < n; i ++) {
        if(!vis[i]) {
            return i;
        }
    }
}
int main()
{
    int x, k;
    while (scanf("%d", &n) != EOF) {
        memset(g, -1, sizeof(g));
        memset(mp, 0, sizeof(mp));
        for (int i = 0; i < n; i ++) {
            scanf("%d", &k);
            if(k == 0) {
                g[i] = 0;
            }
//          mp[i].clear();
            while (k --) {
                scanf("%d", &x);
//              mp[i].push_back(x);
                mp[i][x] = 1;
            }
        }
        for (int i = 0; i < n; i ++) {
            if(g[i] == -1) {
                g[i] = dfs(i);
            }
        }
        while (scanf("%d", &m)!= EOF, m) {
            int res = 0;
            while (m --) {
                scanf("%d", &k);
                res ^= g[k];
            }
            if(res) {
                printf("WINn");
            }
            else {
                printf("LOSEn");
            }
        }
    }
    return 0;
}

最后

以上就是坚定音响为你收集整理的POJ 2425 A Chess Game（SG函数的有向图博弈游戏）的全部内容，希望文章能够帮你解决POJ 2425 A Chess Game（SG函数的有向图博弈游戏）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。