[关闭]
@ysner 2018-08-18T02:20:41.000000Z 字数 1687 阅读 2125

[CF888G]Xor-MST

最小生成树 脑洞


题面

给定一个个节点的完全图,每个节点有个编号,节点和节点之间边的权值为,求该图的最小生成树的权值和。

解析

有个新奇的最小生成树算法:
算法:
先对于每个点,选择在所有与之相连的边中,权值最小的边,并将这条边加入到最小生成树中。
显然这样连出来的边会形成一个森林,并且连边后连通块个数至少减半。
然后我们将每个连通块再看成一个点,重复以上算法即可。
时间复杂度

从高位往低位贪心。
把所有点按当前位为还是分为两类。
显然这两类内部会形成联通块。

然后这两类间一定会有连边。
根据上面那个算法,如果我们选出两类数之间边权最小的那条边,这条边一定在最小生成树中。
因为这是当前状态下(两个大连通块)运行算法后将得到的结果。
接下来分治对两类数内部进行处理。

找边权最小值,直接树即可。

总复杂度

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define pb push_back
  12. #define max(a,b) ((a)>(b)?(a):(b))
  13. #define min(a,b) ((a)<(b)?(a):(b))
  14. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  15. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  16. using namespace std;
  17. const int mod=1e9+7,N=2e5+100;
  18. int n,tot,rt,t[N<<5][2];
  19. il ll gi()
  20. {
  21. re ll x=0,t=1;
  22. re char ch=getchar();
  23. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  24. if(ch=='-') t=-1,ch=getchar();
  25. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  26. return x*t;
  27. }
  28. il void Insert(re int &u,re int x,re int d)
  29. {
  30. if(!u) u=++tot,t[u][0]=t[u][1]=0;
  31. if(d<0) return;
  32. Insert(t[u][(x>>d)&1],x,d-1);
  33. }
  34. il int Query(re int u,re int x,re int d)
  35. {
  36. if(d<0) return 0;re int c=(x>>d)&1;
  37. if(t[u][c]) return Query(t[u][c],x,d-1);
  38. if(t[u][c^1]) return Query(t[u][c^1],x,d-1)^(1<<d);
  39. return 0;
  40. }
  41. il ll solve(vector<int>a,re int d)
  42. {
  43. if(!a.size()||d<0) return 0;
  44. vector<int>b[2];re int mn=0;
  45. for(re int i=0;i<a.size();i++) b[(a[i]>>d)&1].pb(a[i]);
  46. if(b[0].size()&&b[1].size())
  47. {
  48. tot=rt=0;mn=1<<(d+1);
  49. for(re int i=0;i<b[0].size();i++) Insert(rt,b[0][i],30);
  50. for(re int i=0;i<b[1].size();i++) mn=min(mn,Query(rt,b[1][i],30));
  51. }
  52. return mn+solve(b[0],d-1)+solve(b[1],d-1);
  53. }
  54. int main()
  55. {
  56. n=gi();vector<int>a;
  57. fp(i,1,n) a.pb(gi());
  58. printf("%lld\n",solve(a,30));
  59. return 0;
  60. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注