POJ 2599 A funny game (搜索，博弈)
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目：有一棵无向树，从某个结点出发，两个人轮流移动，走过的结点不能再走。
http://poj.org/problem?id=2599
更多的可能就是搜索，用到的博弈知识，只是P/N态的常识
必胜态的后继中必然有一个是必败态。剩下的就是DFS。
题目结点1000，由于是树，所以时限是够的
#include<iostream>#include<cstdio>#include<ctime>#include<cstring>#include<algorithm>#include<cstdlib>#include<vector>#define C 240#define TIME 10#define inf 1<<25#define LL long longusing namespace std;int mmap[1005][1005];int n,k;bool flag[1005];int ret;int slove(int m){ for(int i=1;i<=n;i++) if(mmap[m][i]&&!flag[i]){ flag[m]=true; if(!slove(i)){ flag[m]=false; ret=i; return true; } flag[m]=false; } return false;}int main(){ while(scanf("%d%d",&n,&k)!=EOF){ memset(mmap,0,sizeof(mmap)); for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); mmap[u][v]=mmap[v][u]=1; } memset(flag,false,sizeof(flag)); int ans=slove(k); if(ans==0) puts("First player loses"); else printf("First player wins flying to airport %d\n",ret); } return 0;}