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}$真的有点快！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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);
}