mst

https://www.zybuluo.com/ysner/note/1245941

题面

给一个\(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;

}

巴特西

mst