牛客多校五 B.Graph【最小异或生成树】

题意：

　　给定一棵无根树，可以添加边使之存在环，添加或删除都需要满足环上异或和为0，求最后的最小生成树

做法：

　　把树通过dfs处理异或和添加边变成一个无向完全图，在这张图上面跑Boruvka算法求最小生成树

　　Boruvka算法可以解决需要对边之间进行一定处理后的最小生成树问题

CODE

  1 #include <bits/stdc++.h>
  2 #define dbug(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5  
  6 using namespace std;
  7 typedef long long LL;
  8  
  9 const int inf = 0x3f3f3f3f;
 10  
 11 template<class T>inline void read(T &res)
 12 {
 13    char c;T flag=1;
 14    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 15    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 16 }
 17 
 18 const int maxn = 2e5 + 7;
 19 
 20 int n;
 21 int edge[maxn << 1], head[maxn << 1], nxt[maxn << 1], len[maxn << 1], cnt;
 22 vector<int> a;
 23 
 24 //01字典树
 25 struct Tire {
 26     int ch[maxn * 31][2], l[maxn * 31], r[maxn * 31];
 27     int sz[maxn * 31];
 28     int siz = 0;
 29     LL ans = 0;
 30     void insert(int num) {
 31         int u = 0;
 32         for ( int i = 29; i >= 0; --i ) {
 33             int id = (a[num] >> i) & 1;
 34             if(!ch[u][id]) {
 35                 ch[u][id] = ++siz;
 36                 memset(ch[siz], 0, sizeof(siz));
 37                 l[siz] = r[siz] = num;
 38             }
 39             u = ch[u][id], ++sz[u], l[u] = min(l[u], num), r[u] = max(r[u], num);
 40         }
 41     }
 42 
 43     int find(int u, int dep, int val) {
 44         if(!dep || l[u] == r[u]) {
 45             return a[l[u]];
 46         }
 47         int id = (val >> (dep - 1)) & 1;
 48         if(ch[u][id]) {
 49             return find(ch[u][id], dep - 1, val);
 50         }
 51         else {
 52             return find(ch[u][id ^ 1], dep - 1, val);
 53         }
 54     }
 55 
 56     void dfs(int u, int dep) {
 57         if(!dep) {
 58             return;
 59         }
 60         int ls = ch[u][0], rs = ch[u][1];
 61         if(ls && rs) {
 62             LL res = 1e17;
 63             if(sz[ls] <= sz[rs]) {
 64                 for ( int i = l[ls]; i <= r[ls]; ++i ) {
 65                     res = min(res, 1ll * a[i] ^ find(rs, dep - 1, a[i]));
 66                 }
 67             }
 68             else {
 69                 for ( int i = l[rs]; i <= r[rs]; ++i ) {
 70                     res = min(res, 1ll * a[i] ^ find(ls, dep - 1, a[i]));
 71                 }
 72             }
 73             ans += res;
 74         }
 75         if(sz[ls] > 1) {
 76             dfs(ls, dep - 1);
 77         }
 78         if(sz[rs] > 1) {
 79             dfs(rs, dep - 1);
 80         }
 81     }
 82 
 83     void init() {
 84         memset(sz, 0, sizeof(sz));
 85         memset(ch[0], 0, sizeof(ch[0]));
 86         siz = ans = 0;
 87     }
 88 } trie;
 89 //01字典树
 90 
 91 void BuildGraph(int u, int v, int w) {
 92     ++cnt;
 93     edge[cnt] = v;
 94     nxt[cnt] = head[u];
 95     head[u] = cnt;
 96     len[cnt] = w;
 97 }
 98 
 99 void dfs(int u, int fa, int val) {
100     a.push_back(val);
101     for ( int i = head[u]; i; i = nxt[i] ) {
102         int v = edge[i];
103         if(v == fa) {
104             continue;
105         }
106         dfs(v, u, val ^ len[i]);
107     }
108 }
109 int main() 
110 {
111     read(n);
112     int u, v, w;
113     for ( int i = 1; i <= n - 1; ++i ) {
114         read(u); read(v); read(w);
115         ++u, ++v;
116         BuildGraph(u, v, w);
117         BuildGraph(v, u, w);
118     }
119     dfs(1, 0, 0);
120     sort(a.begin(), a.end());
121     a.erase(unique(a.begin(), a.end()), a.end());
122     trie.init();
123     int len = a.size();
124     for ( int i = 0; i <= len - 1; ++i ) {
125         trie.insert(i);
126     }
127     trie.dfs(0, 30);
128     cout << trie.ans << endl;
129     return 0;
130 }

View Code