題目鏈接：點(diǎn)擊查看

題目大意：給出一棵樹，每條邊都有一個(gè)權(quán)值，每次操作可以刪除任意一條邊或者增加任意權(quán)值的一條邊，現(xiàn)在可以執(zhí)行數(shù)次操作，不過任何時(shí)間都要滿足以下兩個(gè)條件：

n 個(gè)點(diǎn)互相連通

所有環(huán)的權(quán)值異或和為 0

求數(shù)次操作后圖上邊權(quán)之和的最小值

題目分析：將題意轉(zhuǎn)換一下就可以轉(zhuǎn)換為經(jīng)典問題：完全圖上的最小生成樹，給出 n 個(gè)點(diǎn)，每個(gè)點(diǎn)都有權(quán)值 a[ i ] ，每條邊的權(quán)值為 a[ i ] ^ a[ j ] 現(xiàn)在需要求最小生成樹

這個(gè)題目只需要 dfs 跑一遍就可以轉(zhuǎn)換為上述問題了，這里不多贅述，那么將問題轉(zhuǎn)換后，該如何求解呢

有個(gè) boruvka 算法也是求解最小生成樹問題的，只不過是克魯斯卡爾算法和普雷姆算法的結(jié)合版本，具體就是維護(hù)圖中的所有連通塊，然后貪心去找每一個(gè)連通塊和其余所有的連通塊之間的最小邊權(quán)，將其合并為一個(gè)連通塊，如此往復(fù)

那么和這個(gè)題目有什么聯(lián)系呢？首先拋出一個(gè)問題：把當(dāng)前圖的點(diǎn)集隨意劃分成兩半，遞歸兩半后選出連接兩個(gè)點(diǎn)集的邊中權(quán)值最小的一條，得到最后的最小生成樹。

乍一看沒什么問題，但仔細(xì)想一下就會(huì)發(fā)現(xiàn)這個(gè)策略其實(shí)是錯(cuò)誤的，因?yàn)樽罱K的最小生成樹中可能有兩條連接當(dāng)前層兩個(gè)點(diǎn)集的邊

但是對于本題而言，我們可以借助01字典樹劃分點(diǎn)集，借一下圖：https://www.cnblogs.com/qieqiemin/p/13381095.html

當(dāng)我們在字典樹上從最高位到最低位維護(hù)每一個(gè)數(shù)字后，顯然每一個(gè)節(jié)點(diǎn)的左右兩個(gè)兒子，就已經(jīng)將所有的點(diǎn)劃分為兩個(gè)集合了

以上圖中的劃分方法為例，假設(shè)兩個(gè)集合是從第 deep 層的高度分開，顯然兩個(gè)集合中 deep 往上的位置在二進(jìn)制下都是相同的，不同的只是 deep - 1 及往下的位置，所以合并上圖中兩個(gè)綠色集合中的點(diǎn)集所需要的最小代價(jià)就是：(1<<deep)+找到兩個(gè)點(diǎn) i 和 j ，滿足點(diǎn) i 屬于左邊的點(diǎn)集，j 屬于右邊的點(diǎn)集，同時(shí) a[ i ] ^ a[ j ] 是最小的

這樣貪心由下往上去合并的話，上面那個(gè)錯(cuò)誤的策略，在這個(gè)題目中的正確性得到了保證

綜上所述，總結(jié)一下本題的求解方法，在計(jì)算出每個(gè)點(diǎn)的權(quán)值后，將其放入01字典樹中，然后對于每一層深度分治即可，需要注意的幾個(gè)地方就是，這個(gè)題目每個(gè)點(diǎn)的范圍是 0 ~ n-1 ，而不是 1 ~ n，還有就是對于點(diǎn)權(quán)相同的點(diǎn)來說，我們可以想象在其之間建立一條邊，因?yàn)榛ㄙM(fèi)為 0 ，所以不會(huì)對答案造成影響，故在處理時(shí)，對點(diǎn)權(quán)去重一下可以減少時(shí)間復(fù)雜度

至于實(shí)現(xiàn)，對于每次左右子樹中的兩個(gè)連通塊，我是vector暴力維護(hù)的點(diǎn)集（向上傳遞完畢后不要忘記及時(shí)初始化，防止爆內(nèi)存），然后遍歷點(diǎn)集數(shù)更小的連通塊，在另一個(gè)連通塊中找異或值最小的答案，這個(gè)就是01字典樹的基本應(yīng)用了，所以字典樹在本題中共有兩個(gè)用途，一個(gè)是基本應(yīng)用，也就是貪心去查找異或值最小的答案，另一個(gè)是結(jié)合最小生成樹的貪心策略，將其分塊處理

時(shí)間復(fù)雜度的話，因?yàn)樽值錁涞母叨葹?0，所以分治+vector暴力維護(hù)點(diǎn)集的時(shí)間復(fù)雜度為 nlogn，加上需要在字典樹上查找異或的最小值，需要多加一個(gè)log，總的時(shí)間復(fù)雜度也就是 nlognlogn 了

代碼打注釋了，有不理解的地方看看代碼應(yīng)該就明白了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Node {int to,w;Node(int to,int w):to(to),w(w){} };vector<Node>node[N];vector<int>p[N*32],a;int trie[N*32][2],cnt=1;int newnode()//動(dòng)態(tài)初始化 {cnt++;trie[cnt][0]=trie[cnt][1]=0;return cnt; }void insert(int x)//字典樹的插入 {int pos=1;for(int i=30;i>=0;i--){int to=(x>>i)&1;if(!trie[pos][to])trie[pos][to]=newnode();pos=trie[pos][to];}p[pos].push_back(x); }int search(int x,int pos,int deep)//字典樹的查詢，x:需要查詢的值，pos:當(dāng)前根節(jié)點(diǎn)，deep:深度 {int ans=0;for(int i=deep;i>=0;i--){int to=(x>>i)&1;if(trie[pos][to])pos=trie[pos][to];else{pos=trie[pos][!to];ans|=(1<<i);}}return ans; }void dfs(int u,int fa,int val) {a.push_back(val);for(auto it:node[u]){int v=it.to,w=it.w;if(v==fa)continue;dfs(v,u,val^w);} }int query(int ls,int rs,int deep)//在ls的子樹和rs的子樹中找到權(quán)值最小的邊 {int ans=INT_MAX;if(ls>rs)swap(ls,rs);for(int i=0;i<p[ls].size();i++)//暴力枚舉大小較小的一個(gè)點(diǎn)集，logn去另一個(gè)點(diǎn)集中查詢ans=min(ans,search(p[ls][i],rs,deep-1));return ans; }LL solve(int rt,int deep)//分治，rt:根節(jié)點(diǎn)，deep:深度 {LL ans=0;int ls=trie[rt][0],rs=trie[rt][1];if(ls)//記錄左子樹中連通塊的答案ans+=solve(ls,deep-1);if(rs)//記錄右子樹中連通塊的答案ans+=solve(rs,deep-1);if(ls&&rs)//如果需要合并，找到異或和最小的邊進(jìn)行連接ans+=query(ls,rs,deep)+(1<<deep);p[rt].insert(p[rt].end(),p[ls].begin(),p[ls].end());//暴力維護(hù)點(diǎn)集p[rt].insert(p[rt].end(),p[rs].begin(),p[rs].end());p[ls].resize(0),p[rs].resize(0);//別忘了重置return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false); int n;scanf("%d",&n);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);u++,v++;node[u].push_back(Node(v,w));node[v].push_back(Node(u,w));}dfs(1,-1,0);//將邊權(quán)轉(zhuǎn)換為點(diǎn)權(quán)sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end());//離散化去重for(auto v:a)//將不同的點(diǎn)插入到字典樹中insert(v);printf("%lld\n",solve(1,30));return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客多校5 - Graph(字典树+分治求最小生成树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。