题解：P17166 [CEOI 2026] Flower Cutting

· · 题解

题意简述

给定一张无向图。若两个不相邻结点有至少两个公共邻点，就可以连接这两个结点。

输入的图已经无法继续加边。现在删去尽量多的边，要求反复执行上述操作后仍能恢复原图。求最多可以删去多少条边。

解题思路

先确定原图的结构。

取原图中的一条边 (u,v)，并令集合 C 包含 u,v 以及它们的全部公共邻点。任取 C 中两个不同于 u,v 的结点 x,y，它们都有公共邻点 u,v。由于原图已经无法继续加边，(x,y) 一定存在。因此 C 是一个团。

任何包含 (u,v) 的团，其余结点都必须同时与 u,v 相邻，所以都包含于 C。因此，C 正是包含 (u,v) 的唯一极大团。

由此得到两个重要结论：

一次加边及其四条见证边，在原图中位于同一个四结点团，也就位于同一个极大团。不同极大团之间不会相互帮助。因此，可以分别求出每个极大团内部最多删除的边数，再将答案相加。

设大小为 s 的完全图至少需要保留 f(s) 条边。结论为：

f(s)=\left\lceil\frac{3s}{2}\right\rceil-2

先给出达到该边数的构造。

当 s 为偶数时，选择两个结点 a,b，保留边 (a,b)，再将其余结点两两配对。对每一对 (x,y)，保留 (a,x),(x,y),(y,b)。四个结点 a,x,y,b 形成四元环，能够补成团。所有配对处理完后，每个结点都与 a,b 相邻，于是不同配对之间的缺边也能依靠 a,b 补出。

保留的边数为：

1+\frac{3(s-2)}{2}=\frac{3s}{2}-2

当 s 为奇数时，先按上述方式处理 s-1 个结点，再把最后一个结点与 a,b 相连。核心团恢复后，最后一个结点与其余结点都有公共邻点 a,b，所以也能恢复成完整的团。此时恰好保留 \lceil 3s/2\rceil-2 条边。

下面证明不可能保留更少的边。

把每条初始保留边看成一个只含两个结点的团簇。团簇记录一组初始边，并保证这些边能够生长成该团簇结点集上的完全图。初始团簇本身就是二结点完全图，因此满足这一性质。

在生长过程中，一次操作会遇到一个四元环。若环上的边来自多个团簇，就合并所有涉及的团簇。环的两条对角线可以先被补出，使四个环上结点成为团。每个旧团簇都含有一条环边，所以旧团簇中的其他结点可以借助这条边的两个端点连接到整个四结点团。之后，不同旧团簇中的结点也有两个公共邻点，故合并后的结点集能够生长成团。

若还有团簇与新团簇共用至少两个结点，也可以用这两个公共结点补齐两团之间的边，并将它吸收。反复吸收后，不同团簇至多共用一个结点。

对团簇 D，记其中的初始边数为 e(D)。归纳证明如下不等式始终成立：

e(D)\ge\frac{3|D|}{2}-2

初始团簇有两个结点和一条边，恰好取等。

考虑一次四元环合并。设环上共出现 q 个不同团簇，各团簇大小之和为 S，合并后的结点并集为 U。环上的团簇标号沿一周至少变化 q 次，每次变化对应一个被相邻团簇重复计算的环上结点。因此：

S\ge |U|+q

又因为 2\le q\le4，由归纳假设可得：

\begin{aligned} e(U) & \ge\frac{3S}{2}-2q \\ & \ge\frac{3|U|}{2}-\frac{q}{2} \\ & \ge\frac{3|U|}{2}-2 \end{aligned}

再考虑吸收一个团簇 D。设它与当前团簇 U 共有 r\ge2 个结点，则：

\begin{aligned} e(U\cup D) & \ge\frac{3|U|}{2}-2+\frac{3|D|}{2}-2 \\ & =\frac{3|U\cup D|}{2}+\frac{3r}{2}-4 \\ & \ge\frac{3|U\cup D|}{2}-2 \end{aligned}

所以每次合并和吸收都保持不等式。若初始图能够生长为 K_s，上述过程最终会把所有初始边并入同一个大小为 s 的团簇。于是初始边数至少为 3s/2-2。边数必须为整数，因此至少为 \lceil3s/2\rceil-2，与构造相符。

最后考虑如何枚举极大团。对于一条尚未处理的边 (u,v)，其极大团就是 u,v 与全部公共邻点。用压位数组保存邻接关系，可以按位与求出公共邻点。找到团后，标记团内所有边，保证该团只计算一次。

大小为 s 的团能够删除：

\binom{s}{2}-\left(\left\lceil\frac{3s}{2}\right\rceil-2\right)

设机器字长为 w。所有团内边互不重复，标记边的总次数为 O(m)。总时间复杂度为 O(mn/w+m)，空间复杂度为 O(n^2+m)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
const int N=1005;
const int M=100005;
const int W=16;
int eu[M],ev[M],id[N][N],c[N];
ull g[N][W];
bool vis[M];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>eu[i]>>ev[i];
        id[eu[i]][ev[i]]=id[ev[i]][eu[i]]=i;
        g[eu[i]][ev[i]>>6]|=1ull<<(ev[i]&63);
        g[ev[i]][eu[i]>>6]|=1ull<<(eu[i]&63);
    }
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        if(vis[i])continue;
        int cnt=0;
        c[++cnt]=eu[i];
        c[++cnt]=ev[i];
        for(int j=0;j<W;j++)
        {
            ull x=g[eu[i]][j]&g[ev[i]][j];
            while(x)
            {
                c[++cnt]=j*64+__builtin_ctzll(x);
                x&=x-1;
            }
        }
        for(int j=1;j<=cnt;j++)
        {
            for(int k=j+1;k<=cnt;k++)vis[id[c[j]][c[k]]]=1;
        }
        int keep=(3*cnt+1)/2-2;
        ans+=cnt*(cnt-1)/2-keep;
    }
    cout<<ans<<'\n';
    return 0;
}