CF906C题解

0 前言

某天上午闲着摸鱼的时候看zqq说他们模拟赛出了道很水的紫，于是乎过来品鉴一下。

1 题意

给你一个 $n$ 个点 $m$ 条边的无向联通图,你每次可以选择一个点,让跟这个点直接相连的点之间两两连边(原来有边的就不用连),问至少进行几次操作才能使这个图变成完全图,并输出任意一种可行的选择序列.

2 思路

一眼 $m\leq 22$,状压.

这道题看上去没啥思路,但是可以稍作转化.

我们假设用 $now$ 来表示当前图的状态,假设 $now$ 第 $a,b,c,d\dots$ 位为 $1$ ,那么就表示 $a,b,c,d\dots$ 这些点在图中任意两点之间都有一条连边(也就是 $a,b,c,d\dots$ 构成了这个图的一个完全子图 ).

然后,我们用 $f_i$ 表示最少能通过几次操作把图变成 $i$ 状态.那么显然的,答案就是 $f_{2^n-1}$.

然后我们来考虑转移.

一种显而易见你的转移方式就是,我们来用当前状态下,已经包含(已经在目前的完全子图中)的点所直接相连的点来更新当前状态.也就是说,假设当前图的状态为 $i$ ,选择了一个点 $j\in i$ ,假设 $j$ 及其相连的点所构成的集合是 $st_j$,那么显然的有 $f_{i|st_j}=f_i+1$ 当且仅当 $f_{i|st_j}>f_i+1$.然后我们就可以枚举 $i$ 和 $j$ 来转移了.最后输出 $f_{2^n-1}$.

3 实现

这里之所以把"实现"单独拿出来说,是因为这里有一些实现上的细节需要注意.

首先,我们可以在连边的时候,直接记录 $st_i$.需要注意的一点是不要忘了记录自己,也就是 $st_i|=(1<<i)$.

然后还有一个问题是,如何记录选择序列.

有一个比较简单的方法是,记录 $lst_i$ 表示状态 $i$ 是由哪个状态转移过来的 ,也就是使得 $f_i=f_{lst_i}+1$.初始化,我们使 $lst_{st_i}=i$.

除此之外,我们用 $ans_i$ 表示 $lst_i$ 是加了哪一个点来转移到 $i$ 的.

然后,我们就可以在最后的时候,从 $2^n-1$ 开始,不断的令 $i=lst_i$,然后输出 $ans_i$.直到跳不了的时候结束.

整体没啥难的,代码如下:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x&-x)
#define elif else if
int read(){
    int f=1,s=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c-'0');c=getchar();}
    return f*s;
}
int n,m;
int f[1<<23],ans[1<<23],lst[1<<23],st[100];

signed main(){
    n=read(),m=read();
    for(int i=0;i<(1<<n);++i){
        f[i]=0x3f3f3f3f;
    }
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        st[u-1]|=(1<<v-1);//为了方便我们将点的编号都减去1
        st[v-1]|=(1<<u-1);
    }
    if(m==(n*(n-1)/2)){
        printf("0");
        return 0;
    }
    for(int i=0;i<n;++i){
        st[i]|=(1<<i);
        f[st[i]]=1;
        ans[st[i]]=i+1;
    }
    for(int i=1;i<(1<<n);++i){
        if(f[i]==0x3f3f3f3f)continue;
        for(int j=0;j<n;++j){
            if((i&(1<<j))==0)continue;
            if(f[i|st[j]]>f[i]+1){
                f[i|st[j]]=f[i]+1;
                lst[i|st[j]]=i;
                ans[i|st[j]]=j+1;//记录的时候要将点的编号加回来
            }
        }
    }
    printf("%lld\n",f[(1<<n)-1]);
    for(int i=(1<<n)-1;i;i=lst[i]){
        printf("%lld ",ans[i]);
    }
}

4 后记

还是感谢zqq的题解.