博弈论

隔膜。（

二分图博弈

给定一张二分图，两人轮流移动棋子，最终不能移动者负。判定先手是否存在必胜策略。

结论：若起点一定在最大匹配内则先手必胜，反之先手必败。

感性理解，若起点不一定在最大匹配内，就意味着存在从起点出发的增广路。后手可以将棋子沿增广路移动，使得先手必败。

[COCI2017-2018#5] Planinarenje

模板题。考虑如何判定每个山峰是否一定在最大匹配中。

直接网络流复杂度过高。可以使用匈牙利算法，对于每个未匹配的点跑增广路，此时经过的山峰都有可能不在最大匹配中出现。

[NOI2011] 兔兔与蛋蛋游戏

早期 NOI 特有的奇妙题目名。

考虑将空格看成模型中的棋子。对棋盘黑白染色，不妨设空格一开始在黑格。那么，每一步操作可以将空格移动到黑格的黑子或者白格的白子上。

空格的移动路径显然无法构成环。于是对于相邻且相互可达的子建边，原问题就转化为了标准的二分图博弈。

注意到每次操作必然使得一颗子不可用（黑子从黑格走到白格、白子从白格走到黑格），每次操作完后删去即可，顺带更新最大匹配以及判定是否存在必胜策略。