博弈论
贾志豪论文上的题目……题解请看论文
Orz了一下Hzwer
Source Code
Problem: User: sdfzyhy
Memory: 716K Time: 0MS
Language: G++ Result: Accepted Source Code //POJ 3710
#include<cstdio>
#include<cstring>
#include<iostream>
#define F(i,j,n) for(int i=j;i<=n;++i)
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,INF=~0u>>;
const double eps=1e-;
/*******************template********************/
int to[N],next[N],head[N],cnt,s[N],top;
bool vis[N],ve[N],w[N];
void add(int x,int y){
to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt;
}
int dfs(int x){
vis[x]=;
int ans=;
s[++top]=x;
for(int i=head[x];i;i=next[i])
if(!ve[i]){
ve[i]=ve[i^]=;
int temp;
if (!vis[to[i]]) temp=dfs(to[i])+;
else{
int q=s[top--];
while(q!=to[i]){
w[q]=;//环上节点标记
q=s[top--];
}
++top;
return ;
}//缩环
if(w[to[i]]) ans^=temp%;
else ans^=temp;
}
return ans;
}
void clear(){
memset(head,,sizeof head);
memset(next,,sizeof next);
memset(vis,,sizeof vis);
memset(ve,,sizeof ve);
memset(w,,sizeof w);
top=; cnt=;
}
int main(){
int T,n,m,x,y;
while(scanf("%d",&T)!=EOF){
int ans=;
F(i,,T){
clear();
n=getint(); m=getint();
F(i,,m){
x=getint(); y=getint();
add(x,y);
}
ans^=dfs();
}
puts(ans ? "Sally" : "Harry");
}
return ;
}