题解 CF1305G 【Kuroni and Antihype】

liuyongle · 2020-11-15 18:30:37 · 题解

有一张 n 个点的图，点有点权 a_i。两点 i,j 有边当且仅当 a_i \operatorname{bitans} a_j = 0。求一棵生成有向森林，所有边都指向叶子节点，边权为边的起点的点权。最大化有向森林边权和。

n , a_i \leq 2 \times 10^5n

考虑添加一个点权为 0 的点，将边权变为两端点点权和，并将 ans 减去 \sum a_i；这样得到的答案和原问题是一样的。这样就把原题意的生成有向森林转化为了生成树。

考虑采用 \texttt{Kruskal} 算法，从大到小枚举边权和 x，枚举 x 的子集 i，将点权为 i 与 i \operatorname{bitxor} x 的点缩点并计算贡献。

时间复杂度 O(3^{18} \alpha (n))。

代码：

#include<bits/stdc++.h>
template<class T> inline void read(T &x){
  x=0; register char c=getchar(); register bool f=0;
  while(!isdigit(c))f^=c=='-',c=getchar();
  while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
const int N=2.7e5;
int n,max,lim,a[N],fa[N],cnt[N];
long long ans;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int u,int v,long long w){
  if(cnt[u]&&cnt[v]){
    u=find(u),v=find(v);
    if(u!=v){
      // printf("merge %d[%d] %d[%d] => %lld * %d\n",u,cnt[u],v,cnt[v],w,cnt[u]+cnt[v]-1);
      ans+=w*(cnt[u]+cnt[v]-1);
      fa[u]=v,cnt[v]=1;
    }
  }
}
int main(){
#ifdef memset0
  freopen("1.in","r",stdin);
#endif
  read(n),cnt[0]=1;
  for(int i=1;i<=n;i++){
    read(a[i]),cnt[a[i]]++;
    ans-=a[i];
    max=std::max(max,a[i]);
  }
  int lim=1<<32-__builtin_clz(max);
  for(int i=0;i<lim;i++)fa[i]=i;
  for(int i=lim-1;~i;i--){
    for(int j=i;j;j=(j-1)&i)if(cnt[j]&&cnt[i^j])merge(j,i^j,i);
    merge(i,0,i);
  }
  printf("%lld\n",ans);
}