题意:一个N个点的拓扑图,有M个棋子,两个人轮流操作,每次操作可以把一个点的棋子移动到它的一个后继点上(每个点可以放多个棋子),直到不能操作,问先手是否赢。

思路:DFS求每个点的SG值,没有后继的点为必败点。

注意搜索中初始化的问题。

#include<stdio.h>
#include<string.h>
const int N=,M=N*N;
struct node{
int v,next;
}e[M];
int head[N],cnt,in[N],out[N],n,sg[N],p[N];
void add(int u,int v){
e[cnt].v=v,e[cnt].next=head[u];
head[u]=cnt++;
}
int SG(int u){
if(!out[u]) return sg[u]=;
for(int i=head[u];i!=-;i=e[i].next){
int v=e[i].v;
if(sg[v]==-) sg[v]=SG(v);
}
memset(p,,sizeof(p));
for(int i=head[u];i!=-;i=e[i].next){
p[sg[e[i].v]]=;
}
for(int i=;i<n;i++){
if(!p[i]){
return sg[u]=i;
}
}
}
int main(){
int m,k,i,u,v;
while(~scanf("%d",&n)){
memset(head,-,sizeof(head));
memset(sg,-,sizeof(sg));
memset(in,,sizeof(in));
cnt=;
for(i=;i<n;i++){
scanf("%d",&k);out[i]=k;
while(k--){
scanf("%d",&v);
add(i,v);in[v]++;
}
}
for(i=;i<n;i++){
if(!in[i]){
SG(i);
}
}
while(~scanf("%d",&m)&&m){
int ans=;
while(m--){
scanf("%d",&u);
ans^=sg[u];
}
if(ans) puts("WIN");
else puts("LOSE");
}
}
return ;
}

最新文章

  1. atitit.attilax的软件 架构 理念.docx
  2. linux ssh远程免登陆
  3. Mac Pro 编译安装 Redis-3.2.3
  4. vc中获取磁盘IO统计计数
  5. phpcms的评论改为留言板研究
  6. 树形DP+二分(Information Disturbing HDU3586)
  7. 中文系统下,UTF-8编码文本文件读取导致的错误
  8. UVALive 4223 Trucking 二分+spfa
  9. App是什么,可以分为几类?及其相关解释。
  10. PHP提高编程效率的方法,你知道多少呢?
  11. 云计算之路-阿里云上-容器难容:容器服务故障以及自建 docker swarm 集群故障
  12. 071、如何定制calico网络的IP池(2019-04-16 周二)
  13. C++设计模式——访问者模式
  14. docker常用操作备忘
  15. BZOJ 2521: [Shoi2010]最小生成树(最小割)
  16. 利用LVS+Keepalived搭建Mysql双主复制高可用负载均衡环境
  17. Python 19 Django 详解
  18. 鸟哥Linux私房菜基础学习篇学习笔记2
  19. Linux运维之每日小技巧-检测网站状态以及PV、UV等介绍
  20. udp用户数据报协议

热门文章

  1. 背水一战 Windows 10 (37) - 控件(弹出类): MessageDialog, ContentDialog
  2. 【Java每日一题】20161213
  3. luogg_java学习_09_泛型_集合
  4. css3相册图片3D旋转展示特效
  5. 原生JS:JSON对象详解
  6. Android开发重点难点1:RelativeLayout(相对布局)详解
  7. SharePoint 2013 安装中间出错了怎么办? 每一次安装都是一段曲折的路【1603(0x643) 】
  8. 列表屏幕(List Screen)
  9. Java—字符串小结
  10. app:clean classes Exception