「博弈」二分图游戏小结

🤤阿恺🤤我的阿恺🤤还有我的kyjj🤤

模型及结论

对于一类特出的博弈模型，满足以下条件：

1. 博弈人数为两个的一般平等博弈
2. 博弈状态可以分为两类点，人操作的时候只能把一类状态转移到另一种状态。
3. 不可以走到已经走过的状态
4. 无法转移者判负。

显然按照之前DAG博弈的套路，我们把当前的局面建图，因为每个人只能走到一类点，所以这个图是一个二分图。

• 结论是：如果初始局面一定在最大匹配中，那么先手必胜，否则后手必胜。

我们在下面来解释一下这句话的具体意思。

证明

首先我们考虑先手赢的情况， 显然就是操作出来的那条链长度为奇数并且不可扩展，也就是先手走到最后后手走不了了。

那么先手输的情况就是对称的：操作链长度为偶数。

看看现在我们所得到的：二分图，长度为奇数和偶数的链。这让我们联想到的什么？没错，增广路和交替路（homo特有的无端联想 大嘘）。

既然想到了这一步，我们不妨想一想，先手必胜的条件是什么，就是无论后手怎么操作，先手总能通过引导走出一条长度为奇数的链。那么对于一个二分图，什么样的点能打到这样的结果，我们不妨先找一个最大匹配，那么如果起点不在最大匹配内部，那么无论先手怎么走，后手只要一直走这个点的匹配点，先手赢就意味着走出了一条增广路，这显然是不可能的，因为最大匹配不可能再找出一条增广路。那么起点就必须在最大匹配内。

但是这样只是保证了后手在配合的情况下可以走出一条奇数的链，因为后手足够聪明，所以这个限制还是不能保证先手必胜，那么考虑对于哪些满足上面条件的局面先手还是会输，就是最后会走出一条交替路，这也就意味着起点可以通过交替路进行增广使得自己不存在于最大匹配中。所以如果我们希望自己必胜，那么起点就不该在任何一条交替路中出现，也就是起点无法被代替，充分性证毕。

然后是必要性：

如果起点不在所有的最大匹配中，我们不妨选择一个包含起点的最大匹配，那么起点显然可以走出一条交替路。这个时候我们不妨令后手策略如下：如果当前的点在交替路上，我们就走交替路的下一条边，否则我们走这个点的匹配边，如果这个点没有匹配边就递归到我们证明过的子问题了，先不考虑这个点的匹配边无法走的问题。

考虑先手如何操作。如果先手在走完某一步之后走到了交替路上，那么后手显然可以沿着交替路再走一步，那么现在先手的局面其实变成了一个弱化的子问题：先手所在的点依然出现在交替路上，这个点依然不会出现在所有最大匹配中，并且原图中还有一些点已经被删掉了，因为众所周知只有一个点的图是无解的，所以我们这样递归下去也会无解。（其实是一个归纳的过程）那也就意味着先手如果想赢，必须走出一条与这个交替路没有交的路径，并且满足长度为奇数。因为第一个限制，所以先手的第一部显然不能直接走这个点的匹配边，所以先手的第一步一定走的是非匹配边，最后一个点也是非匹配边，并且这两个点之间不是互相匹配的，那这条路径就是一条增广路，显然不存在，必要性证毕。

实现

那么现在的问题是如何找到这个图中所有的出现在所有最大匹配中的点。

nigga algorithm

我们先跑出原图的最大匹配，然后删掉每个点后再跑最大匹配，最大匹配减少意味着这个点不可或缺，但是复杂度很垃圾。

Gaoba algorithm

注：此处的Gaoba为adj. 表示 聪明的、聪慧的、可爱的🤤

考虑二分图求最大匹配的经典做法：最大流，我们将源点连向左边的点，内部的边由左边连向右边，右边的点连向汇点，跑出的最大流就是最大匹配。

考虑一个左边的点如果不在所有的最大匹配，要么源点连向它的边依然存在（也就是他没贡献给最大流，他不在这个最大匹配中），要么就是在残余网络上存在一条源点到他的可行路径，我们走过这条路径再走这个点到源点的反相边，就实现了一次退流，递归到了第一种情况。所以综上所述，我们只要从源点开始走残余网络上可行边，能到达的左边的点都没有出现在所有最大匹配中，剩下那些不可达的点才是出现在所有最大匹配中的点。

右边的点同理，我们只要在残余网络的反图上搜一遍（因为一个点没有贡献是他没有留到汇点，所以是返图），能到达的右边的点就是不可行的，剩下的点才是不可或缺的。

如果对于一些特殊的题目，我们只需要求出左边的可行的点，并且你是使用 dinic 求的最大流，那么可以用一种更简单的写法，利用最后一次的 BFS 留下 dis 数组可以简单的找到每个点是否可以由源点达到。