邯郸做移动网站的地方,网站开发一般会用到什么语言,wordpress用户密码表,dw做的网站怎么题意#xff1a;
给定多个无向有环图#xff0c;两个人在树上博弈#xff0c;问博弈结果。
思路#xff1a;
如果没有环#xff0c;则是一个标准的树上博弈#xff0c;那么满足 1. 叶子节点的sg为0 2. 中间节点的sg为所有儿子节点的sg1的异或和
存在环的话#xf…题意
给定多个无向有环图两个人在树上博弈问博弈结果。
思路
如果没有环则是一个标准的树上博弈那么满足 1. 叶子节点的sg为0 2. 中间节点的sg为所有儿子节点的sg1的异或和
存在环的话可以缩点偶数是0奇数为1具体证明看《组合游戏略述——浅谈SG游戏的若干拓展及变形》
#include cstdio
#include iostream
#include cstring
#include vector
using namespace std;const int N1005;
bool vis[N];
int ve[N],s[N],w[N],top;
int to[N],next[N],head[N],cnt;
void addedge(int u,int v){to[cnt]v;next[cnt]head[u];head[u]cnt;to[cnt]u;next[cnt]head[v];head[v]cnt;
}
int dfs(int u){vis[u]1;int ans0;s[top]u;int tt,v;for (int ihead[u];i;inext[i]){if(!ve[i]) {ve[i]1;ve[i^1]1;vto[i];if(!vis[v]) ttdfs(v)1;else{int qs[top--];while(q!v) w[q]1 , qs[top--];top;return 1;}if(w[v]) ans^(tt%2);else ans^tt;}}return ans;
}
void init(int n){//for (int i0;in;i) g[i].clear();memset(head,0,sizeof(head));memset(next,-1,sizeof(next));memset(vis,0,sizeof(vis));memset(ve,0,sizeof(ve));memset(w,0,sizeof(w));top0;cnt1;
}
int main(int argc, char const *argv[])
{int T,n,m;while (~scanf(%d,T)){int ans0;while (T--){scanf(%d%d,n,m);init(n);for (int i0;im;i){int u,v;scanf(%d%d,u,v);addedge(u,v);}ans^dfs(1);}if (ans) puts(Sally);else puts(Harry);}return 0;
}
