题解：P6989 [NEERC 2014] Epic Win!

· · 题解

确定性做法。（感谢 @whiteqwq 老师的讲解 /bx）

容易发现，当我们知道 bot 的起点，我们是很好构造一张图使得拥有 100 \% 的胜率的。具体操作就是把 bot 的图贺过来，然后把点权全部变成能克 bot 的手势，然后再把边权换成 bot 出的手势。这样就稳赢了。

但问题在于我们不知道起点。

考虑在知道起点的情况只保留获胜的边。那么我们在构造出这张图后，如果在和 bot 大战的过程中发现，我们根本停不下来，那么就说明我们的这张图所认定的 bot 起点就是 bot 真正的起点，那么我们就赢了。

考虑到这一特性，我们充分发扬人类智慧，对于每一个 bot 可能的起点构造一个只保留获胜边的图，平局或失败的边连向下一层的该点。这样为什么是对的？因为总有一层能做到完胜 bot，而我们走到完胜 bot 的层后就会在这一层无限游走。而又因为切换一层等同于一次失败，我们最多在切换 n-1 次后可以到达完胜 bot 的层，因此在 10^9 次游戏中我们最多只会输 99 次。胜率远高于 99 \%。

代码好写，就不放了。