DMOPC ’22 Contest 5 P5 – Twos and Threes
2023-06-25
·
via 某岛
June 25, 2023
题意：给定一个含有障碍的棋盘，问是否可以用 1×2、1×3、和长度 3 的 L 形多米诺骨牌完美覆盖。
分析：先弱化问题，考虑如果只有多米诺骨牌，那么判断是否能铺满只需要二分图匹配即可，进一步如果我们考虑 L 形，可以用网络流建模，参考 这个题。因此基本思想可能是某种网络流？
看起来也确实如此，每个点至少连 1 个，至多连 2 个，所以上下界网络流即可。
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。
