不知道哪个朝代的解题报告

H - The Problem to Make You Happy

Description

Alice and Bob are good friends, as in every other storyline. One day Alice and Bob are playing an interesting game. The game is played on a directed graph with n vertices and m edges, Alice and Bob have exactly one chess piece each. Initially, Bob’s chess piece is placed on vertex x, while Alice’s chess piece is placed at vertex y. Bob plays first, then Alice, then Bob, then Alice and so on.
During each move, the player must move his/her chess piece from the vertex his/her chess piececurrently at to an adjacent vertex, by traveling through exactly one directed edge.(Remember that the game is played on a directed graph.) If someone can’t make such a move, he/she will be considered to lose the game.
There’s one additional rule: at any time, if Bob and Alice’s chess pieces are at the same vertex,then Alice is consider to be the winner and the game ends up immediately.
Now you are given the initial situation, could you determine who is the winner? Please note that neither Bob nor Alice will make any mistakes during the game, i.e. they both play optimally. In case that the game never ends up, Bob is considered to be the winner.

Input

The first line of the input gives the number of test cases, T. T test cases follow.
For each test case, the first line contains two integers n and m ( $2 ≤ n ≤ 100, 1 ≤ m ≤ n × (n − 1)$ ).
Next m lines, each line contains two integers b and e, indicating there is one directed edge from vertex
b to vertex e. Last line contains two integers x and y ( $1 ≤ x, y ≤ n, x \ne y$ ), which are Bob and Alice’s
initial position. The graph contains no self-loops or duplicate edges.

Output

For each test case output one line ‘Case #x: y’, where x is the case number (starting from 1) and y
is ‘Yes’ (without quotes) if Bob can win or the game never ends up, otherwise ‘No’ (without quotes).

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3
5 3
1 2
3 4
4 5
3 1
4 3
1 2
2 3
3 4
1 2
3 3
1 2
2 3
3 1
2 1

Sample Output

1
2
3
Case #1: Yes
Case #2: No
Case #3: Yes

考虑采用 $dp[i][j][k]$ 表示Alice在点i而Bob在点j的情况,k为0或者1代表Bob或者Alice行动,值表示此状态下Alice是否必胜(Bob是否必败);则题目所求即为$dp[x][y][0]$的值。

分析规则可以得到某些显然的确定状态:

1.棋子重合, $dp[i][i][0]=1$ 和 $dp[i][i][1]=1$ ( $1 ≤i≤ n$ )

2.有一人无法行动,即对于所有出度为0的点 $v$ , $dp[v][i][0]=1,dp[i][v][1]=0$

一种思路是使用记忆化搜索,即从 $dp[x][y][0]$ 出发模拟两人的策略:

Bob行动时会尽可能选择所有Alice的必败态:

若对于所有可达状态 $dp[v][j][1]=1$ ,则 $dp[i][j][0]=1$ ,否则 $dp[i][j][0]=0$

Alice行动时会尽可能选择所有Alice的必胜态:

若对于所有可达状态 $dp[i][v][0]=0$ ,则 $dp[i][j][1]=0$ ,否则 $dp[i][j][1]=1$

这种思路的问题在于无法确定永远无法结束,Bob获胜的情况。

因此使用上述已知的确定状态(Alice获胜的状态)构建反图,进行逆向扩展得到所有Alice的必胜态:

对于确定状态 $dp[i][j][0]=1$ ,反图中所有可达状态 $dp[i][v][1]=1$ ,这是Alice主动选择的结果。

对于确定状态 $dp[i][j][1]=1$ ,仅当反图中可达状态 $dp[v][j][0]$ 的后续状态均为Alice的必胜态,即总状态数量上等于 $v$ 的出度时,有 $dp[v][j][0]=1$ ,这是Bob被动决定的结果。

扩展后若有 $dp[x][y][0]=1$ 则Alice胜,否则Bob胜。

参考代码

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
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
bool dp[105][105][2];
int now[105][105][2];
struct edge
{
int n;
edge* next;
}mem[10005],*head[105];
int T,cnt,b,e,x,y,n,m;
int outd[105];
struct sta
{
int x,y,f;
}tmp;
queue<sta> q;
void add_edge(int a,int b)
{
mem[++cnt].n=b;
mem[cnt].next=head[a];
head[a]=mem+cnt;
}
void bfs()
{
for (int i=1;i<=n;i++)
{
tmp.x=tmp.y=i;
tmp.f=0;q.push(tmp);
tmp.f=1;q.push(tmp);
dp[i][i][0]=dp[i][i][1]=1;
if (!outd[i])
for (int j=1;j<=n;j++)
{
if (i==j) continue;
tmp.x=i;tmp.y=j;tmp.f=0;
q.push(tmp);
dp[i][j][0]=1;
}
}
while(!q.empty())
{
int nx=q.front().x,ny=q.front().y,nf=q.front().f;
q.pop();
if (nf)
{
for (edge* it=head[nx];it;it=it->next)
{
if (dp[it->n][ny][0]) continue;
now[it->n][ny][0]++;
if (now[it->n][ny][0]==outd[it->n])
{
dp[it->n][ny][0]=1;
tmp.x=it->n;tmp.y=ny;tmp.f=0;
q.push(tmp);
}
}
}
else
{
for (edge* it=head[ny];it;it=it->next)
{
if (dp[nx][it->n][1]) continue;
dp[nx][it->n][1]=1;
tmp.x=nx;tmp.y=it->n;tmp.f=1;
q.push(tmp);
}
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&T);
for (int _=1;_<=T;_++)
{
scanf("%d%d",&n,&m);
cnt=0;
memset(head,0,sizeof(head));
memset(now,0,sizeof(now));
memset(dp,0,sizeof(dp));
memset(outd,0,sizeof(outd));
for (int i=1;i<=m;i++)
{
scanf("%d%d",&b,&e);
add_edge(e,b);
outd[b]++;
}
scanf("%d%d",&x,&y);
bfs();
printf("Case #%d: %s\n",_,dp[x][y][0]==1?"No":"Yes");
}
return 0;
}