P3679 题解

· · 题解

引理：点集 V 在匹配内的充要条件为 V \cap A 能在匹配内且 V \cap B 能在匹配内。

证明（参考了这篇博客）：令 X = V \cap A,Y = V \cap B。则先找出覆盖 X 的原图上的最大匹配和覆盖 Y 的最大匹配，然后把这些边单独拎出来建图。则现在的目标是选出若干条 不交的 边，使得 X 和 Y 均被覆盖。根据定义每个点 deg \le 2，所以连通块只有链和环两种。对于环，只可能是偶环，所以隔一条边取一条边即可；对于链，如果是奇链，则从第一条边开始隔着取；如果是偶链，发现端点同属于左部点或右部点，不可能同时 \in X 或 \in Y。避开不需要覆盖的端点选边即可。

于是现在可以分别对左部点和右部点统计了。

Hall 定理：考虑左部点或右部点的某个点集 S，设 N(S) = \{v | \exists u \in S,(u,v) \in E\}，则 S 有完美匹配的充要条件为 \forall T \subseteq S,|N(T)| \ge |T|。

根据 Hall 定理，状压后对左部点和右部点分别跑一遍高维前缀与就能得出哪些点集有完美匹配。之后由于题目求的是左部点和右部点的点集，做一遍双指针或二分均可。

时间复杂度 O(n2^n)。