CF1305G - Kuroni and Antihype

题目大意

有 \(n\) 个人，每个人有一个权值 \(a_i\)

每个人可以自己选择放入集合，不获得分数

或者一个已经在集合中的人 \(i\) 可以把一个 \(a_i \ \text{and}\ a_j=0\) 的 \(j\) 放入集合，并且获得 \(a_i\) 的分数

求最大得分总和

模型分析

按照原题的模型分析，视 \(a_i\rightarrow a_j\) 为一条权值为 \(a_i\) 边，则实际上求的是 最大外向森林

考虑加入 \(a_0=0\) ，且 \(a_0\) 初始在集合中，一个人自己放入集合视作被 \(0\) 放入集合

那么问题简化为求以0为根的 最大外向树

进一步观察会发现：

在外向树上每个点贡献次数就是 \(a_i\cdot (deg_i-1)\)

那么最大化 \(a_i\cdot (deg_i-1)\) 等价于最大化 \(\sum a_i\cdot deg_i\)

那么我们将一条边的权值 \(a_i\rightarrow a_j\) 改为 \(a_i+a_j\) ，此时边双向权值相同

问题就变成了求最大生成树

计算生成树

只有暴力解法

倒着枚举 \(a_i+a_j=S\) ，枚举 \(S\) 的子集 \(T\) 就能确定两个点

并查集处理加边即可，复杂度为 \(O(\cfrac{3^{18}}{2}\cdot \alpha(n))\)

\(\text{CodeForces}\) 真的有点快！！

const int N=1<<18,INF=1e9+10;

int n,a[N],F[N];
ll ans;
int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]); }

int main(){
	n=rd();
	rep(i,1,n) {
		int x=rd();
		a[x]++,ans-=x;
	}
	a[0]++;
	rep(i,0,N-1) F[i]=i;
	drep(i,N-1,1) {
		for(int S=i,T;(S^i)<=S;S=(S-1)&i) if(a[S] && a[T=S^i] && Find(S)!=Find(T)) {
			ans+=1ll*(a[S]+a[T]-1)*i;
			a[S]=a[T]=1,F[Find(S)]=Find(T);
		}
	}
	printf("%lld\n",ans);
}