题意:给一个有向图和起点,然后只有一名选手,这名选手可以随意挪动棋子,最终不能动的时候走过的边为奇数边为Win并输出路径,否则如果有环输出Draw,否则输出Lose;

题目链接

知道状态数最多只有n*2就可以了,分成先后手考虑。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+;
int vis[N][],top,nxt[N],n,m,x,y,p,to[N],H[N],tot;
bool cir;
int nt[N][];
bool dp[N][];
void add(int u,int v){
++tot;nxt[tot]=H[u];to[tot]=v;H[u]=tot;
}
void dfs(int now,int k){
bool ko=;
if(vis[now][k]==-) return;
vis[now][k]=;
for(int i=H[now];i;i=nxt[i]){
int v=to[i];
ko=;
if((vis[v][k^]==)|(vis[v][k]==)) cir=;
if(vis[v][k^]==) continue;
dfs(v,k^);
if(!k) {
if(!dp[v][k^]) dp[now][k]=,nt[now][k]=v;
}
else {
if(dp[v][k^]) dp[now][k]=,nt[now][k]=v;
}
}
if(!ko) dp[now][k]=;
vis[now][k]=-;
}
void print(int p,int k){
if(!p) {puts("");return;}
printf("%d ",p),print(nt[p][k],k^);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i) dp[i][]=;
for(int i=;i<=n;++i) {
scanf("%d",&x);
while(x--) {
scanf("%d",&y);
add(i,y);
}
}
scanf("%d",&p);
dfs(p,);
if(dp[p][]) puts("Win"),print(p,);
else if(cir) puts("Draw");
else puts("Lose");
}

最新文章

  1. 在UPDATE中更新TOP条数据以及UPDATE更新中使用ORDER BY
  2. matlab 求解线性方程组之范数
  3. JavaScript的面向对象编程(OOP)(一)——类
  4. Spring IoC源码解读——谈谈bean的几种状态
  5. SVN 远程无法联通
  6. 人工免疫算法-python实现
  7. [转]Python中的矩阵转置
  8. 编程基础-msdn编程指南笔记
  9. 【特殊的图+DP】【11月校赛】大家一起玩游戏
  10. 奇葩问题:spring+mybaits项目突然出现其中一些Mapper类找不到
  11. MBProgressHUD 问题
  12. 工作小结(关于webpack)
  13. Django 1.11 release note简明解读
  14. java之SpringMVC配置!配置!配置!
  15. Mysql-自带的一些功能,基本用法(视图,触发器,事务,存储过程,函数,流程控制)
  16. Java-IO流之输入输出流基础示例
  17. To be taught if i am fortunate
  18. PhoenixFD插件流体模拟——UI布局【Dynamics】详解
  19. C语言入坑指南-被遗忘的初始化
  20. Python模块定义和使用

热门文章

  1. Spring5参考指南:基于注解的容器配置
  2. PHP 面试题总结
  3. 3DMAX导出到Unity坐标轴转换问题
  4. 前端程序员难翻身,没有好的学习方法,你永远无法成功,vue.js专题
  5. 图论--最短路--第K短路(IDA*)(IDA Star)模板
  6. A Tile Painting(循环节)
  7. Nginx模块开发(2)————下载文件
  8. SSM框架完整开发流程
  9. 学习Vue第二节,v-cloak,v-text,v-html,v-bind,v-on使用
  10. Spring官网阅读(七)容器的扩展点(二)FactoryBean