假设没有 *，则问题为在 + 和 . 组成的二分图上，一个 + 要匹配两个 .，最多能匹配多少组。把每个 + 拆成两个点，之间连边，且分别连向所有相邻的 .，则答案即为最大匹配减去 + 的个数。对于 *，只需要把拆出来的两个点分别连向横向和纵向相邻的 . 即可。
时间复杂度 $O(n^2m^2)$。
QOJ.ac
QOJ
Discussion #347 for Problem #12211. Angle Beats
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:14:20
Last updated: 2025-12-14 07:14:24
题解
Comments
No comments yet.