Processing math: 100%

题目描述

Alice 和 Bob 在一张有向图 G=(V,E) 上玩游戏,初始时,在某个顶点 s0 上有一枚石子。

每当轮到某个玩家操作时,设石子在顶点 u,则她需要选择顶点 v 满足 (uv)E,然后将石子从 u 移到 v。如果找不到这样的顶点 v,则该玩家输掉游戏。

可以发现,游戏一共有三种状态:Alice 赢 (Bob 输)、Bob 赢 (Alice 输) 和无限进行 (平局)。

她们对这三种状态的排名是不相同的:Alice 最希望无限进行,其次是 Alice 赢,最后是 Bob 赢。Bob 最希望 Bob 赢,其次是 Alice 赢,最后是无限进行

两个人严格会按照上述策略进行 (如,若 Alice 能使游戏无限进行,她决不会赢;同理,若 Bob 能输,她决不会使游戏无限进行)。

求对于每个 s0V,当 Alice 先手和 Bob 先手时,最终游戏的状态。

输入格式

第一行包含两个正整数 n,m (n105;m2×105),分别表示图 G 的顶点数和边数。

接下来 m 行,每行两个正整数 a,b (1a,bn),表示一条从顶点 a 指向顶点 b 的边。保证 G 中没有重边,但可能有自环

输出格式

输出两行,每行一个字符串,分别记为 A,B。每个字符为 W,L,D 之一,分别表示先手赢后手赢无限进行。其中 Ai 表示当 Alice 先手且 s0=i 时,游戏最终的状态,Bi 表示当 Bob 先手且 s0=i 时,游戏最终的状态。

题解

vA 表示现在石子在 v 处且下一步轮到 Alice 的状态,vB 同理。显然,我们就是要得到每个 vAvB 的 (最终) 状态 (Alice 赢,Bob 赢,无限进行)

根据图论的传统定义,用 N+(v) 表示 v 通过一条边可以到达的顶点集合。

对于 N+(vA),规定里面的元素为下一步轮到 Bob 的状态,N+(vB) 里的元素都是下一步轮到 Alice 的状态。


---- Part 1 ----

我们考虑一个状态什么时候可以无限进行

  1. uA无限进行的充分必要条件是,存在 vBN+(uA),使得 vB无限进行

  2. uB无限进行的充分必要条件是,N+(uB) 且对于每个 vAN+(uB),都有 vA无限进行

    (充分性显然,对于必要性,若 N+(uB)=,显然 uBAlice 赢。若存在 vAuB 使得 vA 不是无限进行,那么 B 肯定会将石子从 v 移到 u)

首先,对于 d+(v)=0 (出度为零) 的顶点 v,显然 vA,vB 都是后手赢,总之,不是无限进行

考虑根据有向图博弈的经验,按照拓扑序的逆序进行更新。根据之前粉色的结论,对于边 uBvA,如果 vA 不是无限进行,则可得 uB 不是无限进行;对于 uAvB,如果所有的 vB 都不是无限进行 (即像拓扑排序一样没入度了),则 uA 也被确定为无限进行。

于是,通过上述算法,我们可以得到若干不是无限进行的点。那剩下的点是否一定是无限进行呢?答案是肯定的,证明如下:

证明

设剩下的点的集合为 R。考虑 uARA,先证明 uA无限进行

首先,由算法的过程知,N+(uA)RB,因此存在 vBN+(uA)RB

而因为 vBRB,则由算法的过程知 N+(vB)RA,于是 B 不会输,且无论 B 如何决策,下一步时石子仍在 R 中。

于是 Alice 就有主动权了,她有能力保持游戏无限进行。从而 uA无限进行

对于 uBRB,可以发现 Bob 无论如何只能走向 RA 中的点,于是转化为 Alice 先手的情形,由上面分析知该情形是无限进行的。这说明 uB 的所有后继状态都是无限进行,由粉色结论知 uB 本身也是无限进行

从而我们可以在 O(n+m) 的时间内得到每个点是否是无限进行。


---- Part 2 ----

接下来,考虑一个非无限进行的状态是 Alice 赢还是 Bob 赢

我们将所有无限进行的状态从图中删去,得到新图 G

此时,我们就可以按照传统的有向图博弈的方法去更新了:若一个点存在先负的后继状态,则它一定是先胜;若一个点的所有后继状态都是先胜 (含没有后继状态),则它是先负。

于是还是按照拓扑序的逆序更新即可。当然这里要对于每个顶点 v 同时记录 vA 的剩余入度和 vB 的剩余入度。

但是,G 也不一定是 DAG,因此如果最后遇到了圈,那些点的状态又如何呢?

设剩下的点的集合为 S。考察 uASA,则 N+(uA) 要么在 S 中,要么是 Bob 赢。同理,对 uBSBN+(uB) 中的元素也是要么在 S 中,要么是 Alice 赢

我们证明,这些点的状态都是 Alice 赢

证明

反证法。假设有一个点不是 Alice 赢

首先,显然 S 中的点不可能无限进行,因此它只可能是 Bob 赢

于是,Bob 存在必胜策略。这个必胜策略显然存在一步会离开集合 S,离开集合 S 分为两种情况:

  1. Bob 主动离开集合 S

    而对于 uBSBN+(uB)S 中的所有元素都是 Alice 赢,矛盾。

  2. Alice 被 Bob 逼着离开集合 S

    而对于 uASA,一定有 N+(uA)S=。否则由算法的过程知 uA 就不应该属于 S

    从而 Alice 存在一种策略,使得永远不会被 Bob 逼着离开 S,该情况也矛盾。

这说明,假设 Bob 赢是错误的,又这里的点不可能无限进行,于是这些点都是 Alice 赢

这样我们就确定了所有的点最终的状态,整个算法只需要两次 bfs (类似拓扑排序),故时间复杂度 O(n+m)

代码

#include <bits/stdc++.h>
using std::cin;
using std::cout;

const int N = 100054, M = N * 2;

struct edge {
	int u, v;
	edge (int u0 = 0, int v0 = 0) : u(u0), v(v0) {}
} e[M];

int V, E;
int first[N], next[M];
int deg[N], Deg[N], que[M];
bool leaf[N];
char alice[N], bob[N];

inline void addedge(int u, int v, int id) {e[id] = edge(u, v), next[id] = first[u], first[u] = id;}

void solve_infinity() {
	int i, h, t = 0, x, y;
	for (i = 1; i <= E; ++i) ++deg[e[i].v];
	for (i = 1; i <= V; ++i) if ((leaf[i] = !deg[i])) alice[i] = bob[i] = 1, que[t++] = i, que[t++] = -i;
	for (h = 0; h < t; ++h)
		if ((x = que[h]) > 0) {
			for (i = first[x]; i; i = next[i])
				if (bob[y = e[i].v] == 68) bob[y] = 1, que[t++] = -y;
		} else
			for (i = first[-x]; i; i = next[i])
				if (!--deg[y = e[i].v]) alice[y] = 1, que[t++] = y;
}

void solve_winlose() {
	int i, h, t = 0, x, y;
	for (i = 1; i <= E; ++i) {
		if (alice[e[i].u] == 1) ++deg[e[i].v];
		if (bob[e[i].u] == 1) ++Deg[e[i].v];
	}
	for (i = 1; i <= V; ++i) if (leaf[i]) alice[i] = bob[i] = 76, que[t++] = i, que[t++] = -i;
	for (h = 0; h < t; ++h)
		if ((x = que[h]) > 0) {
			for (i = first[x]; i; i = next[i]) if (bob[y = e[i].v] != 68) {
				if (alice[x] == 76) {
					if (bob[y] == 1) bob[y] = 87, que[t++] = -y;
				} else {
					if (!--deg[y]) bob[y] = 76, que[t++] = -y;
				}
			}
		} else
			for (i = first[-x]; i; i = next[i]) if (alice[y = e[i].v] != 68) {
				if (bob[-x] == 76) {
					if (alice[y] == 1) alice[y] = 87, que[t++] = y;
				} else {
					if (!--Deg[y]) alice[y] = 76, que[t++] = y;
				}
			}
	std::replace(alice + 1, alice + (V + 1), 1, 87),
	std::replace(bob + 1, bob + (V + 1), 1, 76);
}

int main() {
	int i, u, v;
	std::ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> V >> E;
	for (i = 1; i <= E; ++i) cin >> u >> v, addedge(v, u, i);
	memset(alice + 1, 68, V), memset(bob + 1, 68, V),
	solve_infinity(), solve_winlose();
	cout << alice + 1 << '\n' << bob + 1 << '\n';
	return 0;
}

坑1:粉色条件中的 2 不要忘记 N+(uB)=,度数为 0 的点一定是先手必败的。

坑2:点的度数要利用多次,因此不要把上次拓扑排序更改后的 deg 拿来用。