Gym101190G Game On Graph

一道很有意思的题,我也不知道这个题解是否写清楚了。。

设 A 是 Gennady , B 是 Georgiy 。

首先考虑如何找出所有会使游戏无限进行下去的点。这种点分为两种,一种是从这个点,A 先手出发,就会导致最终平局,还有一种是 B 先手出发却会导致不得不平局。

首先考虑所有出度为 $0$ 的点,显然不管谁从这个点先手,游戏都会结束。

由于 A 的决策是尽量平局,所以一个点 A 出发无法平局当且仅当它的所有后继点都是 B 出发会导致不平局的情况。

由于 B 的决策是尽量不平局,所以一个点 B 如果所有后继点中有一个点 A 出发无法平局,那么这个点也是无法平局的。

于是我们可以类似拓扑序来转移。但是这样会导致有些点转移不到。显然这种到不了的点都是不得不平局的点。

然后考虑已经判断出了所有点是否是 A / B 先手必然平局。那么如何得到答案呢?

我们考虑一个点它是否是 A 先手不得不败的,以及一个点是否是 B 先手必胜的。首先我们丢掉所有平局点的情况,然后所有无出度的点都是 A 先手不得不败的。然后这两个状态也可以类似平局互相推出。最后无法被转移到的点,就意味着这些点既不能成为平局点或者被迫平局,也不能决定出 B 的胜利,那么唯一的可能就是它们在一个类似强连通的结构上,在其中某个状态下 B 其实可以走到一个必败点。事实上 B 无法胜利,它并不会愿意游戏无限进行,所以一定会选择自己走到失败点,于是这些无法被转移到的点的状态一定是 A 胜利、B 失败。

复杂度 $O(n+m)$ 。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN];

vi G[MAXN] , Gr[MAXN];
int deg[MAXN] , td[MAXN];
int dw[MAXN][2] , sw[MAXN][2];
queue<pii> Q;

void solve() {
cin >> n >> m;
rep( i , 1 , m ) {
int u , v;
scanf("%d%d",&u,&v);
G[u].pb( v ) , Gr[v].pb( u );
++ deg[u];
}
rep( i , 1 , n ) {
if( !deg[i] ) {
dw[i][0] = dw[i][1] = 1;
Q.emplace( i , 0 ) , Q.emplace( i , 1 );
}
td[i] = deg[i];
}
while( !Q.empty() ) {
int u = Q.front().fi , w = Q.front().se; Q.pop();
for( int v : Gr[u] ) {
if( w == 0 && !dw[v][1] ) {
dw[v][1] = 1;
Q.emplace( v , 1 );
} else if( w == 1 ) {
-- td[v];
if( !td[v] )
Q.emplace( v , 0 ) , dw[v][0] = 1;
}
}
}
rep( i , 1 , n ) {
if( !deg[i] ) {
sw[i][0] = 1;
Q.emplace( i , 0 );
}
if( !dw[i][0] ) sw[i][0] = -1;
if( !dw[i][1] ) sw[i][1] = -1;
td[i] = deg[i];
}
while( !Q.empty() ) {
int u = Q.front().fi , w = Q.front().se; Q.pop();
for( int v : Gr[u] ) {
if( w == 0 && !sw[v][1] ) {
sw[v][1] = 1;
Q.emplace( v , 1 );
} else if( w == 1 && !sw[v][0] ) {
-- td[v];
if( !td[v] )
Q.emplace( v , 0 ) , sw[v][0] = 1;
}
}
}

rep( i , 1 , n ) {
if( !dw[i][0] ) putchar('D');
else if( !sw[i][0] ) putchar('W');
else putchar('L');
}
puts("");
rep( i , 1 , n ) {
if( sw[i][1] > 0 ) putchar('W');
else if( dw[i][1] ) putchar('L');
else putchar('D');
}
puts("");
}

signed main() {
freopen("game.in","r",stdin) , freopen("game.out","w",stdout);
// int T;cin >> T;while( T-- ) solve();
solve();
}

文章作者: yijan
文章链接: https://yijan.co/2021/04/19/gym101190g-game-on-graph/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog