CF1305G-Kuroni and Antihype

CF1305G-Kuroni and Antihype

给定的数据范围是一个弱化版本。

题意

给定 $n$ 个点权 $\{a\}$，并按照规则：对于 $i,j$，如果 $i \& j=0$ 则对 $i,j$ 连边，生成图 $G$。

现在要求 $G$ 中的每个点都要按照如下规则加入集合 $S$：

1. 直接将点 $i$ 加入集合 $S$，贡献为 0；
2. 如果集合中已经存在点 $j$ 且点 $i,j$ 之间存在连边，那么将 $i$ 加入集合 $S$，贡献为 $a_i$。

求最大贡献，$n\leq 2\times10^3,a_i\leq10^9$。

Sol

暴力枚举 $i,j$ 建边，得到图 $G$，此时考虑处理操作。

我们发现两种操作不好处理，但是本质相同，考虑构造一个点权为 $0$ 的点，向所有的点进行连边，那么操作 1 即可转化为操作 2。

我们发现对于所有的点有且仅有被选中一次，按照我们所选取的边建一张新图，那么我们最终会得到一颗树。这是会很容易联想到最小生成树，但是由于贡献和连边的方向有关，我们很难直接处理贡献。

此时考虑容斥，把边赋权为所连边的两点的点权和，即若 $i,j$ 为边所连接的两点，那么边权为 $a_i+a_j$。再在图 $G$ 上跑一遍最大生成树，然后再减去所有选取的点的点权。答案即

$\sum_{u\in edge}w_u-\sum_{u\in node}a_u$

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=2e3+1e1;
const lint INF=1e18+1e9;

struct Edge{
	int u,v,w;
}e[MAXN<<4];
int fa[MAXN],a[MAXN],n,tot;
lint Ans;

void Addedge(int u,int v,int w){
	e[++tot]=(Edge){u,v,w};
	return;
}

int Find(int x){
	return( fa[x]==x ? fa[x] : fa[x]=Find(fa[x]) );
}

void Joint(int u,int v,int w){
	int fu=Find(u),fv=Find(v);
	if(fu!=fv) Ans+=w,fa[fv]=fu;
	return;
}

bool Cmp(Edge A,Edge B){
	return A.w>B.w;
}

int main(void){

	scanf("%d",&n);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=n;i++) a[i]=readint,Ans-=a[i];
	for(int i=1;i<=n;i++) Addedge(i,0,a[i]),Addedge(0,i,a[i]);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(!(a[i]&a[j])){
		if(i!=j) Addedge(i,j,a[i]+a[j]),Addedge(j,i,a[i]+a[j]);
	}
	sort(e+1,e+tot+1,Cmp);
	for(int i=1;i<=tot;i++) Joint(e[i].u,e[i].v,e[i].w);
	printf("%lld\n",Ans);

	return 0;
}