题解：CF1284G Seollal

Wu_Ren · 2022-01-24 08:18:38 · 题解

有一说一，本题解的思想大概是 @p_b_p_b 在一年前提出的，后来本人与其讨论后学会了，但一直拖到昨天才通过此题并补充了证明。

官方题解

考虑生成树是拟阵，黑色点度数大于 2 的图是拟阵，直接拟阵交即可 O(n^3m^3)，足以通过该题。

但拟阵又慢又难写，没关系，这就来点网络流。

网络流做法

加入点 (0,1),(1,0)，都设为白色，然后以其中一个作为根。这样就变成了每个黑色的点都必须有白色儿子，因此一定有黑点向白点的完备匹配。由 Hall 定理，对于任意的黑色点点集 S，与其至少一个点直接相邻的白点点集为 T，|S|\le|T|。

又因为每个黑点的父亲也是白点，所以题目有解必须满足对于任意的黑色点点集 S，与其至少一个点直接相邻的白点点集为 T，|S|<|T|。

此时跑出来的匹配满足以下性质：考虑让黑点向所有相邻的白点连边，白点只向匹配点连边，那么每个强连通块要么是一个匹配，要是是单个白点，并且每个强连通块一定可以到达单个白点。

由于每个黑点都在匹配内，如果此时图不是弱连通相当于原题无解。考虑将边反向，此时每个强连通块都可以被单个白点到达。

我们通过构造可以证明这样一定有解：对每个没有匹配的白点跑 bfs，在尝试扩展时在生成树上加边，显然图弱连通时一定可以跑出一棵生成树。考虑到每个匹配白点一定是被它的匹配点扩展的，且每个黑点一定是被某个白点扩展的，所以每个黑点一定满足度数至少为 2。

复杂度 O(nm\sqrt{nm})。