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

论坛 › 期权论坛 › 编程之家

 选择匿名的用户  2021-6-2 16:23  891  0

题意

分析

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

代码链接

转载于:https://www.cnblogs.com/yqgAKIOI/p/10277621.html

回复

分享到 :

0 人收藏

16级独孤

选择匿名的用户

积分:3875789

帖子:775174

精华:0

+ 关注私信

期权论坛

期权论坛

期权网络科技版权所有: 关于我们; 联系我们; 加入我们; 反馈问题; 免责声明; 积分充值

统一社会信用代码: 积分规则; 网站地图; 爱文库; 下属网站

官方: 新浪微博; 微信公众号
◆

下载: 表情包; App下载

期权论坛

期权论坛

QQ咨询|关于我们|Archiver|手机版|小黑屋|( 辽ICP备15012455号-4 ) Powered by 期权论坛 X3.2 © 2001-2016 期权工具网&期权论坛 Inc.