二进制下传优化AND连边：UOJ176

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135106721

https://vj.imken.moe/contest/600665#problem/E

一个朴素思路是枚举 $p$ ，然后再枚举 $x\&y=p$ ，如果 $x,y$ 不在一起，则连一条边。

考虑优化。如果 $x,y$ 的交集更大，则不是 $p$ 。所以一个思路是取出 $p$ 所有0的位置，然后继续枚举子集，划分成两个子集，重新或上 $p$ 。此时我们找出来的一定两个数与出来一定是 $p$ 。

但是还可以继续优化。我们可以双向奔赴。或者应该是我们重新考虑一下，我们现在枚举了 $p$ 0集合的两个子集 $s,t$ ，满足 $s\subset t$ ，那么 $s,t$ 之前已经合并在一起了，然后我们会先拿 $s$ 去和一个 $u$ 合并，再拿 $t$ 和一个 $u$ 合并，这样子很浪费。于是我们可以考虑下放思路，比如把 $t$ 下放到 $s$ 。当然我们也不用枚举子集来下方，我们按位枚举下放即可。

我们可以判断一下。如果下放的时候是空的，我们直接下放。如果非空，我们就不用下放了。因为我们 $p$ 是从大往小合并的，我们已经肯定在之前进行了合并了，那我们现在就没必要合并了。

#include<cstdio>
using namespace std;
typedef long long LL;
int n,m,a[2<<18],f[2<<18];
LL ans;

int getf(int x){return f[x]?f[x]=getf(f[x]):x;}

int main()
{
	scanf("%d%d",&n,&m);
	for(int x,i=0;i<n;i++)
	{
		scanf("%d",&x);
		if(a[x])ans+=x;
		a[x]=x;
	}
	for(int u,v,i,p=(1<<m)-1;p;p--)
	{
		for(i=0;i<m&&!a[p];i++)
			a[p]=a[p|1<<i];
		u=a[p];
		for(i=0;i<m;i++)
			if((v=a[p|1<<i])&&getf(u)!=getf(v))
				f[getf(u)]=getf(v),ans+=p;
	}
	printf("%lld\n",ans);
	return 0;
}