?
题意：
给定一个图，两个人从起点出发，轮流开飞机，当离开这个点后这个点
就不能使用了，如果轮到谁了谁不能飞了就输了。
必败状态很好找，当一个人在位置s的时候与这个点相连的没有点能用的
时候则必败。然后数据很小，直接暴力搜索就可以AC。
代码如下：
#include #include #include #include #include #include #include #include #define PB push_back #define MP make_pair #define REP(i,n) for(int i=0;i<(n);++i) #define FOR(i,l,h) for(int i=(l);i<=(h);++i) #define DWN(i,h,l) for(int i=(h);i>=(l);--i) #define IFOR(i,h,l,v) for(int i=(h);i<=(l);i+=(v)) #define CLR(vis) memset(vis,0,sizeof(vis)) #define MST(vis,pos) memset(vis,pos,sizeof(vis)) #define MAX3(a,b,c) max(a,max(b,c)) #define MAX4(a,b,c,d) max(max(a,b),max(c,d)) #define MIN3(a,b,c) min(a,min(b,c)) #define MIN4(a,b,c,d) min(min(a,b),min(c,d)) #define PI acos(-1.0) #define INF 1000000000 #define LINF 1000000000000000000LL #define eps 1e-8 #define LL long long using namespace std; const int maxn = 1001; int mp[maxn][maxn]; bool vis[maxn]; int ans,n,s; bool dfs(int id){ FOR(i,1,n){www.sohu.com if(mp[id][i]&&!vis[i]){//遍历图的顺序确保了答案最小 vis[id]=1; if(!dfs(i)){ vis[id]=0; ans=i; return true; } } vis[id]=0; } return false; } int main(){ while(~scanf(%d%d,&n,&s)){ CLR(mp); REP(i,n-1){ int u,v; scanf(%d%d,&u,&v); mp[u][v]=1; mp[v][u]=1; } CLR(vis); if(dfs(s)) printf(First player wins flying to airport %d ,ans); else puts(First player loses); } return 0; }