UVALive-7042 The problem to make you happy-有向图博弈

题目链接

题意：b和a在一个有向图内玩游戏，有n个点m条边。每人一颗棋子，初始位置为x,y。b先手，轮流操作，每次只能走一条有向边。如果谁不能操作他算输。棋子重合的话b输，游戏没有尽头a输。问b能否赢

思路：orz，一道有向图博弈，继上次的史上最难div2后的第二道有向图博弈，wannafly的每日题。有向图博弈的原理都不难，就是倒着推，如果当前是先手必败态那么上一个一定是必胜态，如果当前是必胜态那么如果前继的所有后继都为必胜态上一个才为必败态。这个题也是这个道理。一开始按四种情况写（ab先手,必胜必败），初始状态ab在一起b输a胜，无路可走各自输。于是……写炸了……怎么都写不对（马力不足，现在想想其实还是可以写的，当时漏了几种情况）……于是开始抄题解，发现这个题其实只要记录b的必败态就可以。如果当前是b走，而且必负，那么上一步a走的时候也一定是必负。如果当前是a走，那么仅当上一个的后继全是必败态（也就是a的必胜态）时，上一个必败。这样代码就少了很多很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<stdio.h>
#include<algorithm>
#include<string.h> 
#include<math.h>
#include<queue>
#include<vector>
#include<map>
using namespace std;
struct node  // ans 1 必胜 0 必败    w 0 bob 1 alice
{
	int ans,x,y,w;
};
vector<int>g[200];
int vis[200][200][3];
int dp[200][200][3];
int in[200];
int cnt[200][200][3];
int main()
{
	int T;
	scanf("%d",&T);
	for(int kase=1;kase<=T;kase++)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		int x,y;
		for(int i=1;i<=n;i++)g[i].clear();
		memset(vis,0,sizeof(vis));
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++)
		 for(int j=1;j<=n;j++)
		  for(int k=0;k<=1;k++)dp[i][j][k]=1;
		memset(in,0,sizeof(in));
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			g[v].push_back(u);  //反向建边
			in[u]++;
		}
		scanf("%d%d",&x,&y);
		queue<node>q;
		while(!q.empty())q.pop();
		for(int i=1;i<=n;i++)
		 for(int j=1;j<=n;j++)
		 for(int k=0;k<=1;k++)
		 {
		 	if(i==j)
		 	{
		 		vis[i][j][k]=1;
		 		dp[i][j][k]=0;
		 		node temp;
		 		temp.ans=0;
		 		temp.x=temp.y=i;
		 		temp.w=k;
		 		q.push(temp);
			 }
			 else
			 if(k==0 && in[i]==0)
			 {
			 	//printf("a:%d %d\n",i,j);
			 	vis[i][j][k]=1;
		 		dp[i][j][k]=0;
		 		node temp;
		 		temp.ans=0;
		 		temp.x=i;
		 		temp.y=j;
		 		temp.w=k;
		 		q.push(temp);
			 }
		 }
		while(!q.empty())  //只记录必败态 
		{
			node temp=q.front();
			q.pop();
			//printf("x:%d y:%d w:%d\n",temp.x,temp.y,temp.w);
			if(temp.w==0)   //现在动b   当前必败则上一步动a的时候也必败 
			{
				int l=g[temp.y].size();
				for(int i=0;i<l;i++)
				{
					int v=g[temp.y][i];
					if(vis[temp.x][v][1]==1)continue;
					dp[temp.x][v][1]=0;
					node temp1;
					temp1.x=temp.x;
					temp1.y=v;
					temp1.ans=0;
					temp1.w=1;
					q.push(temp1);
					vis[temp.x][v][1]=1;
				}
			 }
			else   // 当前动a，只有上一步的后继全是b的必败态的时候，上一步才是b的必败态 
			{
				int l=g[temp.x].size();
				for(int i=0;i<l;i++)
				{
					int v=g[temp.x][i];
					if(vis[v][temp.y][0]==1)continue;
					cnt[v][temp.y][0]++;
					if(cnt[v][temp.y][0]==in[v])
					{
						dp[v][temp.y][0]=0;
						node temp1;
						temp1.x=v;
						temp1.y=temp.y;
						temp1.ans=0;
						temp1.w=0;
						q.push(temp1);
						vis[v][temp.y][0]=1;
					}
				}
			 } 
		}
		if(dp[x][y][0]==1)
		 printf("Case #%d: Yes\n",kase);
		 else printf("Case #%d: No\n",kase);
		
	}
	return 0;
}