某岛

… : "…アッカリ~ン . .. . " .. .
June 25, 2023

DMOPC ’22 Contest 5 P5 – Twos and Threes

题意:给定一个含有障碍的棋盘,问是否可以用 1×2、1×3、和长度 3 的 L 形多米诺骨牌完美覆盖。

分析:先弱化问题,考虑如果只有多米诺骨牌,那么判断是否能铺满只需要二分图匹配即可,进一步如果我们考虑 L 形,可以用网络流建模,参考 这个题。因此基本思想可能是某种网络流?

看起来也确实如此,每个点至少连 1 个,至多连 2 个,所以上下界网络流即可。