假设没有 *，则问题为在 + 和 . 组成的二分图上，一个 + 要匹配两个 .，最多能匹配多少组。把每个 + 拆成两个点，之间连边，且分别连向所有相邻的 .，则答案即为最大匹配减去 + 的个数。对于 *，只需要把拆出来的两个点分别连向横向和纵向相邻的 . 即可。
时间复杂度 $O(n^2m^2)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
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.