[LOJ#6033]. 「雅礼集训 2017 Day2」棋盘游戏[二分图博弈、匈牙利算法]

分类: IT文章 • 2022-04-16 18:01:56

题意

二分图博弈经典模型，首先将棋盘二分图染色。
考虑在某个最大匹配中,从非匹配点出发先手必败：先手只能走到匹配点(否则不是最大匹配)，后手只需要一直走匹配边即可，先手操作时不可能走到非匹配点(否则存在增广路，与最大匹配矛盾)，所以先手必败。
容易发现，当且仅当出发点一定在最大匹配中，先手才会胜利。