博弈模型

Nim/SG

单开了一篇。

二分图博弈/无向图地理游戏

给定图，图上有一枚棋子，二人轮流沿边行动，走过的边不能再走，无法行动者输。

当且仅当棋子在所有最大匹配上时，先手必胜。

正确性比较显然。

二分图的情况当且仅当 $S$ 到 $v$ 的边有流量，且残量网络上不存在 $S$ 到 $v$ 的路径。

或者删掉这个点后最大匹配会减一，最大独立集强制不选它会减一。

nfls2024.5.24 P13106 棋盘

$n\times m$ 大小棋盘，每个点至多被放置 $10^9$ 次，开始棋子放置在 $(1,1)$ ，这次放置也算放置。

每次可以立即结束游戏，或将棋子移动到同行或同列但不同的一个位置上。

给定长为 $n$ 的序列 $a$ 和长为 $m$ 的序列 $b$ ， $(i,j)$ 的权值是 $a_i+b_j$ 。

Alice 要让最终位置的权值最小，Bob 要最大，问最终位置的权值是多少。

二分答案 $X$ ，把 $\le X$ 的染黑， $>X$ 的染白，现在 Alice 每次要从黑走到白，Bob 每次要从白走到黑，没出边就似了。

把每个点拆成 $10^9-1$ 个点来限制每个点不能被到那么多次，原来的每条边都变成二分完全图，于是就变成二分图博弈了。

跑匹配肯定跑不了一点，但是你发现 Hall 定理告诉我们 $10^9-1$ 个点等价于一个点。

推导：等价于让 $|N(S)|-|S|$ 最小，所以拆出的点选了一个就要全选让 $|S|$ 最大。

然后就完了。

其实也可以从建出的模型来看，等价于流量是 $1$ 。

还是跑不了匹配，我们可以求最大独立集来解决，等价于把行和列划分成两个集合，求同时在行1和列1里面的白格 + 同时在行2和列2里面的黑格的最大值。

把 $a,b$ 排序，发现行2和列2一定是行列的前缀，于是枚举行前缀，列前缀有单调性，自己画个图理解一下就好。

若 Alice 先手必胜，那么删掉 $(1,1)$ 后必定最大匹配减一，而全集也减一，所以最大独立集此时应该不变。