Alice 和 Bob 在一张有向图 G=(V,E) 上玩游戏,初始时,在某个顶点 s0 上有一枚石子。
每当轮到某个玩家操作时,设石子在顶点 u,则她需要选择顶点 v 满足 (u→v)∈E,然后将石子从 u 移到 v。如果找不到这样的顶点 v,则该玩家输掉游戏。
可以发现,游戏一共有三种状态:Alice 赢 (Bob 输)、Bob 赢 (Alice 输) 和无限进行 (平局)。
她们对这三种状态的排名是不相同的:Alice 最希望无限进行,其次是 Alice 赢,最后是 Bob 赢。Bob 最希望 Bob 赢,其次是 Alice 赢,最后是无限进行。
两个人严格会按照上述策略进行 (如,若 Alice 能使游戏无限进行,她决不会赢;同理,若 Bob 能输,她决不会使游戏无限进行)。
求对于每个 s0∈V,当 Alice 先手和 Bob 先手时,最终游戏的状态。
第一行包含两个正整数 n,m (n≤105;m≤2×105),分别表示图 G 的顶点数和边数。
接下来 m 行,每行两个正整数 a,b (1≤a,b≤n),表示一条从顶点 a 指向顶点 b 的边。保证 G 中没有重边,但可能有自环。
输出两行,每行一个字符串,分别记为 A,B。每个字符为 W,L,D 之一,分别表示先手赢,后手赢和无限进行。其中 Ai 表示当 Alice 先手且 s0=i 时,游戏最终的状态,Bi 表示当 Bob 先手且 s0=i 时,游戏最终的状态。
用 vA 表示现在石子在 v 处且下一步轮到 Alice 的状态,vB 同理。显然,我们就是要得到每个 vA 和 vB 的 (最终) 状态 (Alice 赢,Bob 赢,无限进行)
根据图论的传统定义,用 N+(v) 表示 v 通过一条边可以到达的顶点集合。
对于 N+(vA),规定里面的元素为下一步轮到 Bob 的状态,N+(vB) 里的元素都是下一步轮到 Alice 的状态。
我们考虑一个状态什么时候可以无限进行。
uA 是无限进行的充分必要条件是,存在 vB∈N+(uA),使得 vB 是无限进行。
uB 是无限进行的充分必要条件是,N+(uB)≠∅ 且对于每个 vA∈N+(uB),都有 vA 是无限进行。
(充分性显然,对于必要性,若 N+(uB)=∅,显然 uB 是 Alice 赢。若存在 vA∈uB 使得 vA 不是无限进行,那么 B 肯定会将石子从 v 移到 u)
首先,对于 d+(v)=0 (出度为零) 的顶点 v,显然 vA,vB 都是后手赢,总之,不是无限进行。
考虑根据有向图博弈的经验,按照拓扑序的逆序进行更新。根据之前粉色的结论,对于边 uB→vA,如果 vA 不是无限进行,则可得 uB 不是无限进行;对于 uA→vB,如果所有的 vB 都不是无限进行 (即像拓扑排序一样没入度了),则 uA 也被确定为无限进行。
于是,通过上述算法,我们可以得到若干不是无限进行的点。那剩下的点是否一定是无限进行呢?答案是肯定的,证明如下:
设剩下的点的集合为 R。考虑 uA∈RA,先证明 uA 是无限进行。
首先,由算法的过程知,N+(uA)∩RB≠∅,因此存在 vB∈N+(uA)∩RB。
而因为 vB∈RB,则由算法的过程知 ∅⊂N+(vB)⊆RA,于是 B 不会输,且无论 B 如何决策,下一步时石子仍在 R 中。
于是 Alice 就有主动权了,她有能力保持游戏无限进行。从而 uA 是无限进行。
对于 uB∈RB,可以发现 Bob 无论如何只能走向 RA 中的点,于是转化为 Alice 先手的情形,由上面分析知该情形是无限进行的。这说明 uB 的所有后继状态都是无限进行,由粉色结论知 uB 本身也是无限进行。
从而我们可以在 O(n+m) 的时间内得到每个点是否是无限进行。
接下来,考虑一个非无限进行的状态是 Alice 赢还是 Bob 赢。
我们将所有无限进行的状态从图中删去,得到新图 G′。
此时,我们就可以按照传统的有向图博弈的方法去更新了:若一个点存在先负的后继状态,则它一定是先胜;若一个点的所有后继状态都是先胜 (含没有后继状态),则它是先负。
于是还是按照拓扑序的逆序更新即可。当然这里要对于每个顶点 v 同时记录 vA 的剩余入度和 vB 的剩余入度。
但是,G′ 也不一定是 DAG,因此如果最后遇到了圈,那些点的状态又如何呢?
设剩下的点的集合为 S。考察 uA∈SA,则 N+(uA) 要么在 S 中,要么是 Bob 赢。同理,对 uB∈SB,N+(uB) 中的元素也是要么在 S 中,要么是 Alice 赢。
我们证明,这些点的状态都是 Alice 赢。
反证法。假设有一个点不是 Alice 赢。
首先,显然 S 中的点不可能无限进行,因此它只可能是 Bob 赢。
于是,Bob 存在必胜策略。这个必胜策略显然存在一步会离开集合 S,离开集合 S 分为两种情况:
Bob 主动离开集合 S。
而对于 uB∈SB,N+(uB)∖S 中的所有元素都是 Alice 赢,矛盾。
Alice 被 Bob 逼着离开集合 S。
而对于 uA∈SA,一定有 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
拿来用。