锐客网

  1. 首页 > 睿知 > it技术 > >

Gym - 100548H The Problem to Make You Happy2014-2015 ACM-ICPC, Asia Xian Regional Contest (BFS+博弈)

IT知识ACM-ICPCRegional

【Gym - 100548H The Problem to Make You Happy2014-2015 ACM-ICPC, Asia Xian Regional Contest (BFS+博弈)】天下之事常成于困约，而败于奢靡。这篇文章主要讲述Gym - 100548H The Problem to Make You Happy2014-2015 ACM-ICPC, Asia Xian Regional Contest (BFS+博弈)相关的知识，希望能为你提供帮助。
题意:Bob和Alice在一张有向无环图上移动,给定二者的起点,Bob先手.Bob的失败条件是不能移动或者与Alice相遇.两个人都采取最优策略,求Bob是否会赢
分析:银牌题.先确定所有的失败状态,然后根据这些反向状态BFS.
用(dp[i][j][0or1])表示bob在i点,Alice在j点,当前移动的人是bob还是Alice的情况, bob是否必败.
首先能确定的是 (dp[i][j][0] = dp[i][j][1] = 0), 对于出度为0的点(i),(dp[i][j][0]= 0).
搜索时有两种状态:
一是当前手是Bob,上一次是Alice,因为两者都选择最优策略,所以Alice肯定会选择让Bob的必败的状态,所以能达到该状态的其余状态都是必败态,将其入队列.
二是当前为Alice,上一次是Bob.Bob肯定不会选择让自己必败的状态,除非它的每一个选择都会走到必败态.统计这个前驱状态会走到的必败态的个数,若此个数等于这个前驱点的出度,表示状态出发的所有状态,Bob都是必败,则这个状态也是必败,将其入队列.

#include < bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 1e2+5; int x,y; int dp[MAXN][MAXN][2]; int deg[MAXN]; //出度 int num[MAXN][MAXN]; //失败的标记 struct Edge{ int v,next; }E[MAXN*MAXN] ,rE[MAXN*MAXN]; int rhead[MAXN],rtot,N, M; void init() { memset(num,0,sizeof(num)); memset(deg,0,sizeof(deg)); memset(rhead,-1,sizeof(rhead)); rtot = 0; }void rAddEdge(int u,int v) { rE[rtot] = (Edge){v,rhead[u]}; rhead[u] = rtot++; }struct Node{ int a, b, cur; }; bool BFS() { memset(dp, -1,sizeof(dp)); queue< Node> Q; //从所有的必败态开始反着搜 for(int i=1; i< =N; ++i){ Q.push((Node){i,i,0}); //都是必败态 Q.push((Node){i,i,1}); dp[i][i][0] = dp[i][i][1] = 0; if(!deg[i]){ for(int j=1; j< =N; ++j){ if(j==i) continue; Q.push((Node){i,j,0}); dp[i][j][0] = 0; } } }while(!Q.empty()){ Node x = Q.front(); Q.pop(); int a = x.a , b = x.b, cur = x.cur; int nxt = cur^1; if(!cur){//Bob int u = b; for(int i = rhead[u]; ~i ; i = rE[i].next){ int v = rE[i].v; if(dp[a][v][1] ==-1){ dp[a][v][1] = 0; Q.push((Node){a,v,1}); } } }else{//Alice int u = a; for(int i = rhead[u]; ~i ; i = rE[i].next){ int v = rE[i].v; num[v][b]++; if(num[v][b]> = deg[v] & & dp[v][b][0]==-1){ dp[v][b][0] = 0; Q.push((Node){v,b,0}); } } } } if(dp[x][y][0]==0) return false; return true; }int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int T,cas=1; scanf("%d",& T); while(T--){ init(); scanf("%d %d ",& N, & M); int u, v; while(M--){ scanf("%d %d",& u, & v); rAddEdge(v,u); //反向建图 deg[u]++; } scanf("%d %d", & x , & y); printf("Case #%d: ",cas++); if(BFS()) printf("Yes "); else printf("No "); } return 0; }








    推荐阅读


    上一篇：Android MVVM小结

    下一篇：SpringMVC-HandlerMapping