mst

图论

题面

给一个$n$点完全图，点权均小于$2^m$。定义边权等于两端点点权的与和（即$a_i\&b_i$)。求最大生成树边权和。

• $10pts\ n\leq8000$
• $15pts\ m=1$
• $25pts\ m\leq12$
• $55pts\ m\leq15$
• $90pts\ n\leq10^5,m\leq18$
• $100pts\ n\leq5*10^6,m\leq20$

解析

$10pts$算法

用$Kruskal$搞复杂度为$O(n^2logn)$，会$TLE$。
可以用$O(n^2)$的$Prim$算法。

for(rg int i=1;i<=n;i++) Dis[i]=-Inf;
            Dis[1]=0;   ll Ans=0;
            for(rg int i=1;i<=n;i++)
            {   int Now=0,Maxd=-Inf;
                for(rg int j=1;j<=n;j++)
                    if(!Blue[j]&&Dis[j]>Maxd) Now=j,Maxd=Dis[j];
                Ans+=Maxd,Blue[Now]=1;
                for(rg int j=1;j<=n;j++)
                    if(!Blue[j])  Dis[j]=Max(Dis[j],A[Now]&A[j]);
            }

值得注意的是初始值极小，永远在取$\max$。

$15pts$算法

说明点权只能为$0$或$1$。
$x$个$1$点最多能连$x-1$条边。
$ans=x-1$。

$25pts$算法

注意到如果数值$p$重复出现$x$次，答案加上$(x-1)*p$（相同数值相互连边）后，就可把该数值视为唯一。
于是$n$降到$O(2^{12})=4096$，又可以$Prim$啦。

$55pts$算法

注意到若$a\&b=b$，在$(a,b)$间连边一定最优。于是可以找出每个点$b$的子集（复杂度$O(15n)$)，若存在，优先建边并统计答案。

然后由于剩下点互不包含，点数会降到$C_m^{m/2}$（因为最多的情况是选所有有$m/2$个$1$的二进制数，而这些数因为$1$数量相同，肯定互不包含），似乎又可以暴力了。

$90pts$算法

这个算法很神仙。

论如何求集合中选一个数与当前值进行位运算的$\max$。
（当然先$orz$CJrank1yyb)

如果是暴力的话，我们的方法有两种:

• 对于当前数$x$，暴力计算所有存在的数$a_i$中，$x\bigoplus i$的最大值，这样的复杂度是$O(2^{16})$。
• 对于每个可能出现的数维护一个当前所有数的最大值。即每次插入时，暴力计算所有的答案的最大值，这样子询问的时候可以$O(1)$查询。

两种方法一种是插入$O(1)$，询问$O(n)$，另外一个是插入$O(n)$，询问$O(1)$。
我们把两种东西结合一下，这样可以得到一个$O(n\sqrt{n})$的方法。

我们对于每个数从中间分开，拆成前$8$个二进制位和后$8$个二进制位。
这样子我们可以预处理一个数组$t[i][j]$，
表示集合中一个前$8$位是$i$的数，后$8$位与$j$进行位运算的最大值。

因为位运算是可以按位贪心的，所以对于查询一个数$x$,我们把它拆成$x=a×2^8+b$。
每次先暴力$for$所有可能的前$8$位，找到与$a$能够构成最大值的那些数，然后对于找到的所有数的前八位$p$，直接查$t[p][b]$。
因为前八位更大的数一定更大，那么影响结果的就只剩下后八位了，
把两个部分拼接起来就好了。
这样子暴力$for$前八位的复杂度是$O(2^8)$，查找后面部分最大值的复杂度是$O(1)$
所以这样子总的复杂度$O(2^8)$。
而对于集合中插入一个数，前$8$位唯一确定，每次只需要预处理后$8$位的结果。
时间复杂度还是$O(2^8)$,总的复杂度还是$O(\sqrt{n})$。
最后记得反过来再跑一遍。

照搬该方法到本题，复杂度为$O(n\sqrt{n})$。
注意一下连边。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=1e5+100;
int a[N],h[N],cnt,n,m,k,f[N],p=1,base,nxt[N],t[1<<11][1<<11],c[1<<11][1<<11],cp[N],tl[N],ma[N],fa[N];
ll ans;
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il int find(re int x){return fa[x]?fa[x]=find(fa[x]):x;}
il void link(re int u,re int v)
{
  re int fu=find(u),fv=find(v);
  if(fu^fv)
    {
      nxt[tl[fv]]=h[fu];
      tl[fv]=tl[fu];
      fa[fu]=fv;
      ++p;
    }
}
il void solve()
{
  memset(f,0,sizeof(f));memset(t,-1,sizeof(t));memset(ma,-1,sizeof(ma));
  fp(i,1,n)
    if(!fa[i])
    {
    for(re int j=h[i];j;j=nxt[j])
      {
    re int x=a[j]>>k,y=a[j]&base;//x代表前一半位，y代表后一半位
    fp(z,0,(1<<m-k)-1)//枚举前一半位并统计答案
      if(f[z])
        {
          re int ss=a[j]&t[z][y]|(z<<k&a[j]);//组合
          if(ss>ma[i]) ma[i]=ss,cp[i]=c[z][y];
        }
      }
  for(re int j=h[i];j;j=nxt[j])
    {
      re int x=a[j]>>k,y=a[j]&base;f[x]=1;//标记其存在
      fp(z,0,(1<<k)-1)//枚举后一半位并处理
    if((y&z)>t[x][z]) t[x][z]=y&z,c[x][z]=i;
    }
    }
  memset(f,0,sizeof(f));memset(t,0,sizeof(t));
  fq(i,n,1)
    if(!fa[i])
      {
    for(re int j=h[i];j;j=nxt[j])
      {
    re int x=a[j]>>k,y=a[j]&base;
    fp(z,0,(1<<m-k)-1)
      if(f[z])
        {
          re int ss=a[j]&t[z][y]|(z<<k&a[j]);
          if(ss>ma[i]) ma[i]=ss,cp[i]=c[z][y];
        }
      }
  for(re int j=h[i];j;j=nxt[j])
    {
      re int x=a[j]>>k,y=a[j]&base;f[x]=1;
      fp(z,0,(1<<k)-1)
    if((y&z)>t[x][z]) t[x][z]=y&z,c[x][z]=i;
    }
      }
  fp(i,1,n)
    if(!fa[i])
      {
    re int u=find(i),v=find(cp[i]);
    if(u^v) ans+=ma[i],link(i,cp[i]);
      }
}
int main()
{
  freopen("mst.in","r",stdin);
  freopen("mst.out","w",stdout);
  n=gi();m=gi();k=m/2;base=(1<<k)-1;
  fp(i,1,n)
    {
      a[i]=gi();
      h[i]=tl[i]=i;
    }
  while(p<n) solve();
  printf("%lld\n",ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}

$100pts$算法

倒序枚举用于连接的边权$p$，用$a_p$表示$p$的最大超集（只用多一个$1$）所在联通块的代表元。枚举$p$的另一超集（只用多一个$1$），若两者不在同一联通块，合并之。从大到小保证最优性。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=1e5+100;
int a[1<<21],h[N],cnt,n,m,f[1<<21];
ll ans;
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il int find(re int x){return f[x]?f[x]=find(f[x]):x;}
int main()
{
  freopen("mst.in","r",stdin);
  freopen("mst.out","w",stdout);
  n=gi();m=gi();
  fp(i,1,n)
    {
      re int x=gi();
      if(a[x]) ans+=x;
      a[x]=x;
    }
  fq(t,(1<<m)-1,0)
    {
      re int &u=a[t];
      for(re int i=0;!u&&i<m;i++) u=a[t|(1<<i)];
      if(!u) continue;
      fp(i,0,m-1)
    {
      re int v=a[t|(1<<i)],fu=find(u),fv=find(v);
      if(v&&fu!=fv) ans+=t,f[fv]=fu;
    }
    }
  printf("%lld\n",ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}