求出最大匹配后，首先判断是否 $C=M$，这其实是一个 2-SAT 问题，即一条边两端点至少选一个，不选未匹配点，一对匹配点不能都选。接着判断 $C=M+1$，这也可以通过枚举多选的未匹配点或是两端点都选的匹配边之后 2-SAT 解决。时间复杂度 $O(n^3)$。
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 #321 for Problem #961. Smol Vertex Cover
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:04:43
Last updated: 2025-12-14 07:04:45
题解
Comments
No comments yet.