一类可以转化成有向图上博弈的问题

· · 算法·理论

概述

定义基本规则：

出现平局的根本原因是决策会绕起来成环。我们先来解决如何判断一个点的胜负状态。

首先，如果图是 DAG，则有经典做法：

然后有了环，先给出结论：只需加上这一条即可：

考虑证明。将不满足前三种情况的点称为“状态未知”。

若当前在一个状态未知的点，它一定不满足前三种情况。于是这个点必然满足：出边到达的点中有一些先手必胜，另外的状态未知且存在至少一个这样的点。

这样，当前玩家为了不败，一定不会走那些先手必胜的点，而走向状态未知的点。如此下来，棋子所在的位置永远是状态未知的点，因此游戏不会结束，即为平局。

具体做法是建反图然后 bfs，然后根据当前点的状态与上述规则进行转移。

例题

一个单词可看作是一条边，代表前三个字母的状态走向后三个字母的状态。

比如 abcdef 就是 abc 走向 def。

直接运用上述做法，转化成起点是起始单词的后三个字母，Aoki 先手的游戏。

code

略微修改一下“胜负”的定义，改为“游戏是否会结束”。

定义 end_{u,0/1} 表示 Takahashi/Aoki 在 u 是游戏是否会结束。

对于 u 来说，显然有：

其余情况均为 \text{False}，证明不难。

然后是求以每个点开始游戏时结束后的值 dp_{u,0/1}，表示 Takahashi/Aoki 在 u 是游戏结束后的值。

则有:

dp_{u,0}=\min_{u\to v}dp_{v,1}+w(u,v) dp_{u,1}=\max_{u\to v}dp_{v,0}+w(u,v)

而在用上面方法的时候，dp_{u,0} 的转移会出现一些问题，用普通队列无法保证用到 dp_{u,0} 时它的最优性。

而转移顺序对 dp_{u,1} 没有影响，因为根据上面的做法，只有当所有 u 的出边遍历到以后 u 才会入队。因此考虑使用优先队列（小根堆），保证第一次转移到 dp_{u,0} 时就是最小的。

code

胜负状态与平局都很明确，直接做就行了。

状态有 O(n^6)，表示三个棋子分别在什么位置。

具体地，dp_{x_1,y_1,x_2,y_2,x_3,y_3,0/1} 表示红棋在 (x_1,y_1),(x_2,y_2)，黑棋在 (x_3,y_3)，当前红/黑走时的答案（包含是否必胜与步数）。

与上文一样，而此题边权都是 1，相当于保证了直接用 queue 的正确性（先转移步数少的）。可以与上一题类比成边权为 1 和边权大于 1 的最短路。

轻微卡常，可以把红棋有序变无序，状态数压一半。

code

注：引自我的另一篇文章。

这个题和普通的有向图上博弈不同，加了一个某一方优先选择平局的条件，因此看起来很奇怪。

因为双方目标不同，首先可以想到把每个点拆成 A 先手和 B 先手两个点，我们称希望平局的人为 A，希望结束的人为 B。

为了简化问题，我们先把问题转化为一方不想游戏结束，另一方想要游戏结束。这和 [ABC261Ex] Game on Graph 的第一步相似。我们定义 End_{u,0/1}=0/1 表示 A/B 在 u 先手出发后游戏是否结束（0 否 1 是）。那么有：

简单地说，如果 A 先手，只有出边全都能结束时才能结束；如果 B 先手，只要有出边能结束，他就会选择这条边并结束。

接下来就是确认那些结束点的胜负状态。由于此时两个人都很正常的不想输，那么一个普通的反图拓扑递推就能解决这个问题。具体的，从出度为 0 的点出发拓扑，一路只管能够结束的点进行递推（出边全胜则负，出边可负即胜）即可。 但是此时会有一些点没有被递推到（我称之**状态不确定点**）。这是些什么点呢？那就是：本身能够结束，且出边中只存在**状态不确定点**和必胜点（可能还有平局点，这种情况仅在 $B$ 先手时出现）的点。如何分析这些点的胜负？如下： 如果该**状态不确定点**是 $A$ 先手，那么出边中包含**状态不确定点**和必胜点。其中 $A$ 不想输，所以一定走**状态不确定点**。注意此时这些**状态不确定点**都是确定会让游戏结束的点。 如果该**状态不确定点**是 $B$ 先手，那么出边中包含**状态不确定点**，必胜点和平局点。此时 $B$ 如果再走**状态不确定点**，就和 $A$ 的决策绕起来成环，也就平局了，这是矛盾的。同时为了不平局，$B$ 一定会选择走必胜点，从而该点必败。 此时回头看 $A$ 的决策，我们发现 $A$ 走到下一个**状态不确定点**后，局面是一个是 $B$ 先手的**状态不确定点**，因此 $B$ 必败，相当于 $A$ 必胜。 因此，这些**状态不确定点**中，$A$ 先手的点必胜，$B$ 先手的点必败！ 至此此题结束。