题解 P4136 【谁能赢呢？】

· · 题解

二分图博弈经典题。

所谓二分图博弈，指的是这样一类博弈问题：给出一张二分图，指定图上一点 s 放置一颗棋子。两位玩家交替操作，若当前棋子位于 p 点，玩家需要将棋子移动到与 p 有边相邻，且之前还没有被访问的点，不能操作的玩家判负。

四连通的棋盘显然是二分图：向相邻的点移动只能使横坐标或者纵坐标变化 1，当终点与起点重合时，使横坐标增加的移动次数与使横坐标减少的移动次数相等，故横向移动了偶数次，对纵向的情况同理，故图上不存在奇环。

因此本题满足二分图博弈的模型。

对于二分图博弈，有如下定理成立：若起点 s 在该二分图的所有最大匹配中均为匹配点，则先手必胜，反之先手必败。

证明可以参考 Pecco 的知乎专栏文章，此处不再展开。

由于本题的图论模型比较特殊，我们可以直接进行分类讨论，不必再跑 Dinic 判断 s 是否一定在最大匹配中：