首页 > 代码库 > 【POJ3710】Christmas Game 博弈 有限制的图上删边游戏(树形删边游戏进化1)
【POJ3710】Christmas Game 博弈 有限制的图上删边游戏(树形删边游戏进化1)
转载请注明出处:http://blog.csdn.net/vmurder/article/details/42671885
其实我就是觉得原创的访问量比未授权盗版多有点不爽233。。。
题意:
一个树图,然后1永远是根,两人轮流删边,不能删者输。
删边限制:只能删跟1连通的边。
树图限制:
它首先是一棵树,然后某些点上可能带一个环
原描述:最开始的图是一颗带有一些简单环的树,然后任何边都至多在一个多边形上。每个多边形最多有一个节点出现在主树上。
给个神犇论文地址:
石家庄二中·贾志豪——
《组合游戏略述——浅谈SG游戏的若干拓展及变》
http://wenku.baidu.com/link?url=BV3xf05i4YyrBqgEnkDnTNxeKf85irWoLLY_uVki2aa-nGL6h2yrEww8FKx2DoTq5cxe4NKF2Sl3tj4kvhNvknRbscpdCtKPY3hKDPyZlhW
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 105 #define M 1500 using namespace std; struct KSD { int v,next; }e[M]; int head[N],cnt,newnode,TOT; inline void add(int u,int v) { e[++TOT].v=v; e[TOT].next=head[u]; head[u]=TOT; } int n,m,map[N][N]; int dfn[N],low[N]; int stk[N],top; int flag[N]; void init() { cnt=TOT=top=0; memset(head,0,sizeof head); memset(map,0,sizeof(map)); memset(dfn,0,sizeof(dfn)); memset(flag,0,sizeof(flag)); memset(stk,0,sizeof(stk)); } void tarjan(int x,int p) { int i,u,v,temp; low[x]=dfn[x]=++cnt; stk[++top]=x; for(i=1;i<=n;i++)if(map[x][i]&&i!=p) { if(!dfn[i]) { tarjan(i,x); low[x]=min(low[x],low[i]); if(dfn[x]<=low[i]) { temp=++top; while(stk[--top]!=x); if((temp-top==2&&map[x][i]==1)||(temp-top)&1) { if(!flag[x])flag[x]=u=++newnode;else u=flag[x]; if(!flag[i])v=++newnode;else v=flag[i]; add(u,v); } } } else low[x]=min(low[x],dfn[i]); } return ; } int SG(int x,int p) { int i,v,sg=0; for(i=head[x];i;i=e[i].next) { v=e[i].v; if(v==p)continue; sg^=(SG(v,x)+1); } return sg; } int main() { // freopen("test.in","r",stdin); int i,k,T,a,b; while(scanf("%d",&T)!=EOF) { for(k=0;T--;) { scanf("%d%d",&n,&m); init(); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); map[a][b]++,map[b][a]++; } cnt=0; flag[1]=newnode=1; tarjan(1,0); k^=SG(1,0); } // printf("%d\n",k); if(k)puts("Sally"); else puts("Harry"); } return 0; }
【POJ3710】Christmas Game 博弈 有限制的图上删边游戏(树形删边游戏进化1)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。