概述
定义基本规则：
-
两个玩家轮流移动同一颗棋子。
-
每次移动沿一条出边将棋子移到下一个点。
-
当前玩家走不了（没有出边）时输。
-
图可能有环，游戏无法结束时为平局。
出现平局的根本原因是决策会绕起来成环。我们先来解决如何判断一个点的胜负状态。
首先，如果图是 \(\text{DAG}\)，则有经典做法：
-
没有出边的点先手必败。
-
出边中能走到先手必败点的点先手必胜。
-
所有出边走到的都是先手必胜点的点先手必败。
然后有了环，先给出结论：只需加上这一条即可：
- 建反图，由已知状态倒推，不满足上述任意一种情况的点即为平局。
考虑证明。将不满足前三种情况的点称为“状态未知”。
若当前在一个状态未知的点，它一定不满足前三种情况。于是这个点必然满足：出边到达的点中有一些先手必胜，另外的状态未知且存在至少一个这样的点。
这样，当前玩家为了不败，一定不会走那些先手必胜的点，而走向状态未知的点。如此下来，棋子所在的位置永远是状态未知的点，因此游戏不会结束，即为平局。
具体做法是建反图然后 bfs，然后根据当前点的状态与上述规则进行转移。
例题
一个单词可看作是一条边，代表前三个字母的状态走向后三个字母的状态。
比如 abcdef 就是 abc 走向 def。
直接运用上述做法，转化成起点是起始单词的后三个字母，Aoki 先手的游戏。
略微修改一下“胜负”的定义，改为“游戏是否会结束”。
定义 \(end[u][0/1]\) 表示 Takahashi/Aoki 在 \(u\) 是游戏是否会结束。
对于 \(u\) 来说，显然有：
-
若 \(\forall u \to v,end[v][0]= Ture\)，则 \(end[u][1]=Ture\)。
-
若 \(\exist u \to v,end[v][1]= Ture\)，则 \(end[u][0]=Ture\)。
亦可用上述方法得到 \(end\) 数组，证明不难。
然后是求以每个点开始游戏时结束后的值 \(dp[u][0/1]\)，表示 Takahashi/Aoki 在 \(u\) 是游戏结束后的值。
则有:
\[dp[u][0]=\min_{u\to v}dp[v][1]+w[u\to v] \]\[dp[u][1]=\max_{u\to v}dp[v][0]+w[u\to v] \]而在用上面方法的时候，\(dp[u][0]\) 的转移会出现一些问题，用普通队列无法保证用到 \(dp[u][0]\) 时它的最优性。
而转移顺序对 \(dp[u][1]\) 没有影响，因为根据上面的做法，只有当所有 \(u\) 的出边遍历到以后 \(u\) 才会入队。因此考虑使用优先队列（小根堆），保证第一次转移到 \(dp[u][0]\) 时就是最小的。
胜负状态与平局都很明确，直接做就行了。
状态有 \(O(n^6)\)，表示三个棋子分别在什么位置。
具体地，\(dp[x1][y1][x2][y2][x3][y3][0/1]\) 表示红棋在 \((x1,y1),(x2,y2)\)，黑棋在 \((x3,y3)\)，当前红/黑走时的答案（包含是否必胜与步数）。
与上文一样，而此题边权都是 1，相当于保证了直接用 queue 的正确性（先转移步数少的）。可以与上一题类比成边权为 1 和边权大于 1 的最短路。
轻微卡常，可以把红棋有序变无序，状态数压一半。
标签：状态,有向图,博弈,转化成,先手,出边,end,平局,dp From： https://www.cnblogs.com/jimmywang/p/17338055.html