题解：CF906C Party

Targanzqq · 2024-07-19 21:05:58 · 题解

鉴定为：紫不如蓝。

这是一道经典的状压 dp，dp 转移的过程非常好想，设 f_{i} 表示一个互相认识的朋友集合，我们接下来有两种思路：

一种是枚举它的补集，然后把贡献加进去，但是这样做时间复杂度会太高，所以不行。

还有一种是经典套路，就是枚举一个已经加入的朋友，通过它来找新加入的朋友。设 S_j 是 j 的朋友集合，当前集合为 i ，那我们用 f_i+1 去更新 f_{i|s_j}，让后者去最小值。

还有就是 dfs 的过程，对于可以产生贡献的 f_i+1，我们让 f_{i|s_j} 的转移过程定为 i，最后从 f_{2^n-1} 往回找即可，每次输出转移过程。

然后你就会发现，样例过不了。

但是我们发现，最后的集合都一样，因为这是一个无向图，让谁先认识都一样，中间都是联通的。所以我们正向输出和倒向输出都对。

源代码：

#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,f[1<<22],g[22],fa[(1<<22)],s[(1<<22)],ans[(1<<22)];
int nxt[22];
vector<int> t[22];

void dfs(int now){
    if(fa[now])dfs(fa[now]);
    cout<<ans[now]<<" ";
}

signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<(1<<n);i++){
        f[i]=INF;
    }
    for(int i=0;i<n;i++)g[i]|=(1<<i);
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        t[a-1].push_back(b-1);
        t[b-1].push_back(a-1);
        g[a-1]|=(1<<(b-1));
        g[b-1]|=(1<<(a-1));
    }
    if((n*(n-1)/2)==m){
        cout<<0;return 0;
    }
    for(int i=0;i<n;i++){
        f[g[i]]=1;
        ans[g[i]]=i+1;
    }
    for(int i=0;i<(1<<n);i++){
        if(f[i]==INF)continue;
        for(int j=0;j<n;j++){
            if(!(i&(1<<j)))continue;
            if(f[i]+1<f[i|g[j]]){
                f[i|g[j]]=f[i]+1;
                fa[i|g[j]]=i;
                ans[i|g[j]]=j+1;
            }
        }
    }
    cout<<f[(1<<n)-1]<<endl;
    dfs((1<<n)-1);
}