题解：P17166 [CEOI 2026] Flower Cutting

luqyou · 2026-08-10 21:40:58 · 题解

被硬控了。

手玩一下条件可以发现等价于图中的任意两个极大完全子图边集不交。不难发现不在任意一个完全子图内的边都是不可以删的，因为能被加回去的边加回去后一定在一个 K_4 内部。

那么我们只要找出完全图的答案，然后再找出原图中所有的极大完全子图，将它们的答案相加即可。

对于完全图的情况，n<4 显然不能删除任何边，n=4 时可以删除两条边。接着考虑增量构造（这里我做的时候一直考虑每次只能加一个点，倒闭了好久），只要我们每次在上面接一个点数 \le 4 的环，那就一定可以长成一个完全图。那么加入一个点的时候可以找两个点与它连上，加入两个点的时候找两个点分别与这两个点相连，再将加入的两个点相连即可。

于是完全图被我们解决，现在只需要找出原图中所有极大完全子图即可。

这是简单的。由于所有极大完全子图边不相交，因此只需要枚举每条边 (u,v)，所有同时与 (u,v) 连边的点加上 u,v 就构成了一个极大完全子图。不难使用 bitset 做到 O\left(\dfrac{nm}{w}\right)。