Gym101190G Game On Graph

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

设 A 是 Gennady , B 是 Georgiy 。

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

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

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

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

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

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

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

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

#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();
}

\