ACWing3735 构造完全图(状压dp&思维)

发布于 2021-07-07  127 次阅读


题目大意:

给定一个由 $n$ 个点和 $m$ 条边构成的无重边无自环的无向连通图

我们希望通过以下操作将其变为一个完全图。

  • 每次操作时,选择其中一个点,找到所有和它直接相连的点,使这些点两两之间连边(若两点之间已经存在边,则无需重复连接)。

请问,至少多少次操作以后,可以将整个图变为一个完全图?并要求输出方案。

$1 \le n \le 22$,$1 \le m \le \frac {n (n-1)} {2}$。

解题思路:

我们考虑一种类似于 $Prim$ 算法的做法。

我们从一个原图中的最大团开始(注意一个点本身就是一个团),然后不断向外扩张。

这里的 “扩张” 指的是选择团中一个点,对它进行一次操作,从而把有边与它相连的点加入团中。

ACWing3735-pic1.png

比如上图,因为 $x$ 本身在一个团里,所以 $x$ 原本就一定与团中的所有点相连。而对 $x$ 进行操作后,外部的三个点也与团内部的所有除了 $x$ 之外的点相连,再加上它们本身与 $x$ 相连,所以这三个点就被扩充进团内了。

再联想到 $1 \le n \le 22$,所以很显然可以想到一个 $O(n \times 2^n)$ 的状压 $dp$:设 $f_S$ 表示使目前的极大团是点集 $S$ 的最小操作步数。每次我们选出在团中的一个点,对外进行扩张即可。

状态转移方程:$f[S|to[i]]=\min(f[S|to[i]],f[S]+1)$。其中 $to[i]$ 是与点 $i$ 相邻的点的状态压缩后的集合。题目中要求记录方案,我们在转移时记录状态决策点和前驱状态,最后从结束状态一步一步跳回最初状态,在跳的过程中把决策点(进行操作的点)输出即可。

然后我们就可以进行 $dp$ 了......吗?

群众:这个怎么就是对的呢?我们需要证明!

不,OI 不需要证明。

我们可以发现,这道题的操作,和进行最小生成树的操作是类似的。那既然我们这种构造方法是 $Prim$ 算法,那么我们求最小生成树的另一种算法——$Kruskal$ 算法呢?($Brouvka$ 算法过于冷门,且本质上是 $Prim$ 和 $Kruskal$ 算法的综合,这里就不考虑了)

我们可以发现,$Kruskal$ 算法显然是更一般的情况:在 $Kruskal$ 中,每次进行操作的不一定是极大团中的点。而是东拼西凑从而最后构建成功(农村包围城市)。我们的算法显然没有考虑这种构造方式。

靠,我们的算法不会是假的吧?!

当然......不是。我们可以证明,我们的构造方式虽然不完备,但一定包括了一种最优方案

我们这里有一个结论:想要把点吸收进团内,必然是操作团内部的点。

证明很简单,要扩张 $x$ 进入最大团中时,必然至少存在一个点,在原图中不与 $x$ 连边(否则最大团应该本来就包括了 $x$)。而用题目中给定的操作来操作一个点 $x$ 时,点 $x$ 本身并没有与其他点连边。那么这次操作后 $x$ 还是不能与团中的所有点连边,所以只能操作团内部的点。

ACWing3735-pic2.png

类 $Kruskal$ 做法如上图,我们可以发现在类 $Kruskal$ 的做法中,扩张团 $A$ 与孤立团 $B$ 合并时,必然存在一个同时在 $A$ 和 $B$ 中的点(否则总会有至少一条边连不上)。

我们考虑这个被重叠的点 $x$。我们可以发现,在我们的类 $Prim$ 做法中,我们不先构造孤立团 $B$ ,而是一直扩张 $A$。在扩张过程中选了这个本来被重叠的点 $x$ 后,有可能能白嫖到本来在孤立团 $B$ 中的点,所以这样子一定不会比先类 $Kruskal$ 做法更差。

那么证明就结束了,做上述的状压 $dp$ 即可。

代码(带注释):

#include<bits/stdc++.h>
using namespace std;
const int N=23,M=(1<<22)+5;

struct Path{
    int sta,pt;
}g[M];

int n,m;
int to[M],f[M];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

int main(){
    //freopen("ACWing3735.in","r",stdin);
    //freopen("ACWing3735.out","w",stdout);
    n=read(),m=read();
    for (int i=0;i<n;++i) to[i]=1<<i;
    for (int i=1;i<=m;++i){
        int x=read()-1,y=read()-1;
        to[x]|=(1<<y),to[y]|=(1<<x);
    }
    if (m==(n*(n-1)>>1)){ printf("0\n"); return 0; }        // 特判一开始就是完全图的情况
    memset(f,63,sizeof(f));
    for (int i=0;i<n;++i){
        f[to[i]]=1;
        g[to[i]]=(Path){0,i};
    }
    for (int S=0;S<(1<<n);++S)
        for (int i=0;i<n;++i){
            if (!(S>>i&1)) continue;
            if (f[S|to[i]]>f[S]+1){
                f[S|to[i]]=f[S]+1;
                g[S|to[i]]=(Path){S,i};     // 记录路径
            }
        }
    int Sta=(1<<n)-1;
    printf("%d\n",f[Sta]);
    while (Sta){        // 从最终状态往回跳,在跳的途径中输出答案
        printf("%d ",g[Sta].pt+1);
        Sta=g[Sta].sta;
    }
    printf("\n");
    return 0;
}

我们无法选择过去,但我们可以改变未来。