自动搬运

查看原文

来自洛谷，原作者为

	masterhuang 不要逃避自己的命运

搬运于2025-08-24 23:15:01，当前版本为作者最后更新于2025-04-28 23:58:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}