题意:给定一个含有障碍的棋盘,问是否可以用 1×2、1×3、和长度 3 的 L 形多米诺骨牌完美覆盖。
分析:先弱化问题,考虑如果只有多米诺骨牌,那么判断是否能铺满只需要二分图匹配即可,进一步如果我们考虑 L 形,可以用网络流建模,参考 这个题。因此基本思想可能是某种网络流?
看起来也确实如此,每个点至少连 1 个,至多连 2 个,所以上下界网络流即可。
Posted by xiaodao Category: 日常