题解：P12371 【模板】最大团/最大独立集

· · 题解

std 好菜啊！好菜啊！好菜啊！

本文经过伟大的 EI 的教导。

理论上 std 应该是这个东西《浅谈信息学竞赛中的独立集问题》 - 学习笔记 。

当然也可以看 CF1767E 题解。

时空复杂度 O(2^{n/2})。

最大独立集个数不超过 2^{n/2}，故个数是完全可以用 int 存的。

最大独立集：常见的求最大独立集的乱搞是尝试删度数最大的点。对于这个题，若 \deg \le 2，每个联通块都只是环和链，单独算一下。否则暴力递归，复杂度 T(n)=T(n-1)+T(n-4)\Rightarrow T(n)\sim 1.3803^n，吊打 O(2^{n/2}) 的 std。而且空间也是 O(n) 而非 std 的 O(2^{n/2})。

虽然复杂度可能要 \times n，但是根本跑不满，还可以过程中通过位运算优化只算有效位，跑得飞快。

具体细节详见代码。

//洛谷 P12371
//https://www.luogu.com.cn/problem/P12371
#include<bits/stdc++.h>
#define u64 unsigned long long
#define ctz __builtin_ctzll
#define pc __builtin_popcountll
#define P pair<u64,int>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=55;
int n,m,f[N],g[N];u64 U,e[N];
inline void wr(u64 S){for(;S;S&=(S-1)) cout<<ctz(S)+1<<" ";cout<<"\n";}
P dfs(u64 S)
{
    if(!S) return {0,1};int w=0,d=-1;
    for(u64 i=S;i;i&=(i-1))
    {
        int x=ctz(i),t=pc(e[x]&S);
        if(t>d) d=t,w=x;
    }//找度数最大的点
    if(d<=2)
    {
        u64 v=S,x=0,s1,s2;int y=1;bool O;
        auto dfs=[&](auto &&sf,int x,bool o)->void{
            v^=(1ull<<x);(o?s2:s1)|=1ull<<x;O&=(pc(e[x]&S)==2);
            while(v&e[x]) sf(sf,ctz(v&e[x]),o^1);
        };//搜每个联通块的形态以及点数
        while(v)
        {
            s1=s2=0,O=1;dfs(dfs,ctz(v),0);int a=pc(s1),b=pc(s2),num=a+b;
            (O&&(num&1))?x|=(a<b?s1:s2):x|=(a>b?s1:s2);
            y*=(O?g:f)[num];//f 是链的方案数，g 是环的方案数
        }
        return {x,y};
    }//处理环和链
    u64 W=1ull<<w;P nw=dfs(S^W);
    auto [x,y]=dfs(S&(~(e[w]|W)));x|=W;
    if(pc(x)>pc(nw.first)) nw={x,y};
    else if(pc(x)==pc(nw.first)) nw.second+=y;//递归下去
    return nw;
}
inline void sol(){
    auto [S,c]=dfs(U);
    cout<<pc(S)<<" "<<c<<"\n";wr(S);
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;U=(1ull<<n)-1;
    for(int i=1;i<=n;i++) f[i]=(i&1?1:i/2+1),g[i]=(i&1?i:2);
    for(int i=1,u,v;i<=m;i++) cin>>u>>v,e[--u]|=1ull<<(--v),e[v]|=1ull<<u;
    for(int i=0;i<n;i++) e[i]=((~e[i])&U)^(1ull<<i);sol();//最大团，转补图求最大独立集
    for(int i=0;i<n;i++) e[i]=((~e[i])&U)^(1ull<<i);sol();//求最大独立集
    return 0;
}