题解：P14146 朝花

Shellchen · 2026-03-06 10:53:02 · 题解

这篇文章中定义 K_n 为 n 个结点的完全图。

首先按照构造题的套路，核心修改操作一般是最小的操作，在这题就是取反 K_3。

其次注意到，取反 K_3 并不会改变结点度数的奇偶性。事实上，若 n 为奇数，取反 K_n 不会改变度数的奇偶性，否则会改变涉及到的所有结点的奇偶性。

接着发现，一个所有结点度数为偶数的图可以这样清空：

首先，找到结点编号最小，且度数不为 0 的点 u。接下来，将其所有出点两两配对，对于每一对 (v,w)，对 (u,v,w) 执行操作。重复此过程直到图为空。

很明显，一轮操作对点度数的改变仅有将 u 的度数置为 0，所以这是对的。

现在的目标是把这个图所有点的度数变为偶数。可以使用下面的方法：

首先，把所有度数为奇数的点放到一个数列中，记为 A，并记 |A|=k，显然有 k \mid 2。接下来分情况：

于是做完了。

分析一下代价：

• 一开始变成所有点读书为偶数的图的时候，最多有 \frac{n}{4} 组，每组代价为 16，总代价为 4n，加上最后 6 个点的组，代价为 4n+36。边数每组最多增加 6 条，最多增加 \frac{3n}{2} 条边，加上最后 6 个点的组，边数为 \frac{3n}{2}+15。
• 设变化后边数为 m'，则显然要进行 m' 次操作（每次减少一条边），代价为 9m'，最大为 9m+\frac{27n}{2}+135。

总代价 \frac{35n}{2}+9m+151。

常数有些大，但是前面 n,m 有关的项有 \frac{5n}{2}+m 的余地，还是可以的，而且我前面直接加上 6 个点的组其实 n 会偏大，所以是可以过去的。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const int N=3e6+10,mod=998244353;
pair<int,int>e[N];
int ce;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
int cur;
vector<int>f[N];
int d[N];
bool vis[N];
map<pair<int,int>,int>mp;
void turn(vector<int>vec)
{
    sort(vec.begin(),vec.end());
    f[++cur]=vec;
    for(int i=0;i<vec.size();i++) for(int j=i+1;j<vec.size();j++)
    {
        if(mp[{vec[i],vec[j]}]) mp.erase({vec[i],vec[j]});
        else mp[{vec[i],vec[j]}]=1;
        d[vec[i]]++,d[vec[j]]++;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        pair<int,int>p;
        cin>>p.fi>>p.se;
        if(p.fi>p.se) swap(p.fi,p.se);
        e[i]=p;
        mp[p]=1;
        d[p.fi]++,d[p.se]++;
    }
    vector<int>vec;
    for(int i=1;i<=n;i++) if(d[i]%2!=0) vec.push_back(i);
    if(vec.size()==2)
    {
        int cnt=0;
        for(int i=1;i<=n;i++) if(d[i]%2==0)
        {
            vec.push_back(i);
            cnt++;
            if(cnt==4) break;
        }
        turn(vec);
        turn({vec[2],vec[3],vec[4],vec[5]});
    }
    else if(vec.size()%4==0) for(int i=0;i<vec.size();i+=4) turn({vec[i],vec[i+1],vec[i+2],vec[i+3]});
    else
    {
        for(int i=0;i<vec.size()-6;i+=4) turn({vec[i],vec[i+1],vec[i+2],vec[i+3]});
        turn({vec[vec.size()-6],vec[vec.size()-5],vec[vec.size()-4],vec[vec.size()-3],vec[vec.size()-2],vec[vec.size()-1]});
    }
    for(auto v:mp) if(v.se) pq.push(v.fi);
    while(pq.size())
    {
        auto p=pq.top();pq.pop();
        auto q=pq.top();pq.pop();
        if(p==q) continue;
        pq.push({p.se,q.se});
        f[++cur]={p.fi,p.se,q.se};
    }
    cout<<cur<<'\n';
    for(int i=1;i<=cur;i++)
    {
        cout<<f[i].size()<<' ';
        for(auto v:f[i]) cout<<v<<' ';
        cout<<'\n';
    }
    return 0;
}

:::