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

題面

給定一個\(n\)個節點的完全圖，每個節點有個編號\(a_i\),節點\(i\)和節點\(j\)之間邊的權值為\(a_i\bigoplus a_j\),求該圖的最小生成樹的權值和。

• \(n\leq2*10^5\)

  解析

  有個新奇的最小生成樹算法：
  \(Boruvka\)算法：
  先對于每個點，選擇在所有與之相連的邊中，權值最小的邊，并將這條邊加入到最小生成樹中。
  顯然這樣連出來的邊會形成一個森林，并且連邊后連通塊個數至少減半。
  然后我們將每個連通塊再看成一個點，重復以上算法即可。
  時間復雜度\(O(mlogn)\)。

從高位往低位貪心。
把所有點按當前位為\(0\)還是\(1\)分為兩類。
顯然這兩類內部會形成聯通塊。

然后這兩類間一定會有連邊。
根據上面那個算法，如果我們選出兩類數之間邊權最小的那條邊,這條邊一定在最小生成樹中。
因為這是當前狀態下（兩個大連通塊）運行\(B\)算法后將得到的結果。
接下來分治對兩類數內部進行處理。

找邊權最小值，直接\(Trie\)樹即可。

總復雜度\(O(mlogn)\)。

#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 pb push_back
#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=2e5+100;
int n,tot,rt,t[N<<5][2];
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 void Insert(re int &u,re int x,re int d)
{if(!u) u=++tot,t[u][0]=t[u][1]=0;if(d<0) return;Insert(t[u][(x>>d)&1],x,d-1);
}
il int Query(re int u,re int x,re int d)
{if(d<0) return 0;re int c=(x>>d)&1;if(t[u][c]) return Query(t[u][c],x,d-1);if(t[u][c^1]) return Query(t[u][c^1],x,d-1)^(1<<d);return 0;
}
il ll solve(vector<int>a,re int d)
{if(!a.size()||d<0) return 0;vector<int>b[2];re int mn=0;for(re int i=0;i<a.size();i++) b[(a[i]>>d)&1].pb(a[i]);if(b[0].size()&&b[1].size()){tot=rt=0;mn=1<<(d+1);for(re int i=0;i<b[0].size();i++) Insert(rt,b[0][i],30);for(re int i=0;i<b[1].size();i++) mn=min(mn,Query(rt,b[1][i],30));}return mn+solve(b[0],d-1)+solve(b[1],d-1);
}
int main()
{n=gi();vector<int>a;fp(i,1,n) a.pb(gi());printf("%lld\n",solve(a,30));return 0;
}

轉載于:https://www.cnblogs.com/yanshannan/p/9496053.html

總結

以上是生活随笔為你收集整理的[CF888G]Xor-MST的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。