博弈论------------------移棋子游戏

给定一个有 NN 个节点的有向无环图，图中某些节点上有棋子，两名玩家交替移动棋子。
玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。
对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。
输入格式
第一行，三个整数 N,M,KN,M,K，NN 表示图中节点总数，MM 表示图中边的条数，KK 表示棋子的个数。
接下来 MM 行，每行两个整数 X,YX,Y 表示有一条边从点 XX 出发指向点 YY。
接下来一行， KK 个空格间隔的整数，表示初始时，棋子所在的节点编号。
节点编号从 11 到 NN。
输出格式
若先手胜，输出 win，否则输出 lose。
数据范围
1≤N≤20001≤N≤2000,

1≤M≤60001≤M≤6000,

1≤K≤N1≤K≤N
输入样例：
6 8 4
2 1
2 4
1 4
1 5
4 5
1 3
3 5
3 6
1 2 4 6

输出样例：
win

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 2010, M = 6010;
int h[N], e[M], ne[M], idx;
int f[N];
int n, m, k;
void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int sg(int u){if (f[u] != -1)    return f[u];set<int> S;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];S.insert(sg(j));}for (int i = 0; ; i ++)if (S.count(i) == 0){f[u] = i;break;}return f[u];
}
int main(){scanf("%d%d%d", &n, &m, &k);memset(h, -1, sizeof h);for (int i = 0; i < m; i ++){int a, b;scanf("%d%d", &a, &b);add(a, b);}memset(f, -1, sizeof f);int res = 0;for (int i = 0; i < k; i ++){int u;scanf("%d", &u);res ^= sg(u);}if (res)   puts("win");else       puts("lose");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！