首页 > 代码库 > POJ2599 A funny game (图博弈)
POJ2599 A funny game (图博弈)
题目链接:传送门
题意:
给定一个图,两个人从起点出发,轮流开飞机。当离开这个点后这个点
就不能使用了。假设轮到谁了谁不能飞了就输了。
必败状态非常好找,当一个人在位置s的时候与这个点相连的没有点能用的
时候则必败。
然后数据非常小。直接暴力搜索就能够AC。
代码例如以下:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <set> #include <map> #include <queue> #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){ 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\n",ans); else puts("First player loses"); } return 0; }
POJ2599 A funny game (图博弈)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。