链接: http://uoj.ac/problem/176
对于这种边权难以直接维护的都直接考虑 brouvka 算法.
显然, 我们要做的是实现一个可以查询 & x 最大的数据结构.
可以先对于所有权值建立一颗 01-trie 树.
考虑在 trie 树查询答案的过程, 可以考虑一个从高位到低位的贪心.
当 x 的第 i 位为 1 时, 最优策略一定是能走 1 就走 1.
当 x 的第 i 位为 0 时, 既可以走 0 也可以走 1.
因此可以用一个类似线段树合并的方式, 把每一个 trie 树上的节点右儿子合并到左儿子上.
然后直接按照 brouvka 算法的套路搞一下就行了.
- #include<iostream>
- #include<cctype>
- #include<cstdio>
- #include<cstring>
- #include<string>
- #include<cmath>
- #include<ctime>
- #include<set>
- #include<cstdlib>
- #include<algorithm>
- #define N 220000
- #define L 200000
- #define M 8000000
- #define eps 1e-7
- #define inf 1e9+70
- #define db double
- #define ll long long
- #define ldb long double
- using namespace std;
- inline int read()
- {
- char ch=0;
- int x=0,flag=1;
- while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
- while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
- return x*flag;
- }
- int v[N],f[N];
- int find(int x){if(x!=f[x])f[x]=find(f[x]);return f[x];}
- void merge(int x,int y){f[find(x)]=find(y);}
- struct node{int x,y;}w[N],p[N];
- bool operator<(node a,node b)
- {
- if(a.y!=b.y)return a.y<b.y;
- else return a.x<b.x;
- }
- int n,m,a[N];
- struct Trie
- {
- #define lson lc[o]
- #define rson rc[o]
- int size,root,lc[M],rc[M],maxv[M],mixv[M];
- int newnode()
- {
- int o=++size;
- lson=rson=0;maxv[o]=mixv[o]=-inf;
- return o;
- }
- void upd(int x,int y)
- {
- if(!x||!y)return;
- if(maxv[x]==maxv[y])mixv[x]=max(mixv[x],mixv[y]);
- if(maxv[x]<maxv[y])mixv[x]=max(mixv[x],max(maxv[x],mixv[y]));
- if(maxv[x]>maxv[y])mixv[x]=max(mixv[x],maxv[y]);
- maxv[x]=max(maxv[x],maxv[y]);
- }
- void pushup(int o)
- {
- maxv[o]=mixv[o]=-inf;
- upd(o,lson);upd(o,rson);
- }
- void insert(int &o,int t,int x,int id)
- {
- if(!o)o=newnode();
- if(!t)
- {
- if(maxv[o]>id)mixv[o]=max(mixv[o],id);
- if(maxv[o]<id)mixv[o]=maxv[o],maxv[o]=id;
- return;
- }
- if(!((1<<(t-1))&x))insert(lson,t-1,x,id);
- else insert(rson,t-1,x,id);
- pushup(o);
- }
- int merge(int x,int y)
- {
- if(!x||!y)return x|y;
- int o=newnode();
- lson=merge(lc[x],lc[y]);
- rson=merge(rc[x],rc[y]);
- maxv[o]=mixv[o]=-inf;
- upd(o,x);upd(o,y);
- return o;
- }
- void solve(int o,int t)
- {
- if(!t||!o)return;
- if(lson)solve(lson,t-1);
- if(rson)solve(rson,t-1);
- lson=merge(lson,rson);
- }
- node query(int o,int t,int x,int id)
- {
- if(!t)return (node){(id==maxv[o])?mixv[o]:maxv[o],0};
- if((1<<(t-1))&x)
- {
- if((!rson)||(id==maxv[rson]&&mixv[rson]==-inf))
- return query(lson,t-1,x,id);
- else
- {
- node ans=query(rson,t-1,x,id);
- ans.y+=(1<<(t-1));
- return ans;
- }
- }
- else
- return query(lson,t-1,x,id);
- }
- }T;
- int main()
- {
- n=read(),m=read();
- for(int i=1;i<=n;i++)a[i]=read();
- for(int i=1;i<=n;i++)f[i]=i;
- ll ans=0;
- for(int i=0;i<M-1;i++)T.lc[i]=T.rc[i]=0,T.maxv[i]=T.mixv[i]=-inf;
- int tot=0;
- while(true)
- {
- tot++;
- int cnt=0;
- for(int i=1;i<=n;i++)v[i]=0,f[i]=find(i);
- for(int i=1;i<=n;i++)
- {
- v[f[i]]=max(v[f[i]],i);
- if(i==f[i])cnt++;
- }
- for(int i=1;i<=n;i++)f[i]=v[f[i]];
- if(cnt==1)break;
- for(int i=0;i<=T.size;i++)T.lc[i]=T.rc[i]=0,T.maxv[i]=T.mixv[i]=-inf;
- T.size=T.root=0;
- for(int i=1;i<=n;i++)T.insert(T.root,m,a[i],find(i));
- T.solve(T.root,m);
- for(int i=1;i<=n;i++)w[i]=(node){-1,-1};
- for(int x=1;x<=n;x++)
- {
- int id=find(x);
- node o=T.query(T.root,m,a[x],id);
- w[id]=max(w[id],o);
- }
- int tot=0;
- for(int i=1;i<=n;i++)
- if(w[i].x!=-1)
- {
- int x=w[i].x;
- if(find(i)!=find(w[x].x)||find(i)<find(w[i].x))
- {
- ans+=w[i].y;
- p[++tot]=(node){find(i),find(w[i].x)};
- }
- }
- for(int i=1;i<=tot;i++)merge(p[i].x,p[i].y);
- }
- printf("%lld",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2924814.html