转载请注明出处,谢谢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 long
using 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;
}
分享到:
相关推荐
poj2599,简单dfs可以过此题,按顺序搜到任意可行解即可。
北大POJ1753-Flip Game 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
poj 3901 The Computer Game.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1942-Paths on a Grid 解题报告+AC代码
北大POJ2488-A Knight's Journey 解题报告+AC代码
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
poj分类poj分类poj分类poj分类
北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告