求出最大匹配后，首先判断是否 $C=M$，这其实是一个 2-SAT 问题，即一条边两端点至少选一个，不选未匹配点，一对匹配点不能都选。接着判断 $C=M+1$，这也可以通过枚举多选的未匹配点或是两端点都选的匹配边之后 2-SAT 解决。时间复杂度 $O(n^3)$。
QOJ.ac
QOJ
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.