mst_in_binary
同样,Word版本有特效:mst_in_binary
特别鸣谢YYY和小火车的耐心讲解!
Tag: 位运算最小生成树
【BZOJ 3943】[Usaco2015 Feb] SuperBull
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3943
离线版题目:http://paste.ubuntu.com/23080229/
XOR意义下的位运算生成树
#include<iostream> #include<cstdio> #include<cstring> #define LL long long using namespace std; const int N = 2000+9; const int M = N*32; const int SGZ = 2; int n,arr[N],fa[N],to[N],val[N]; LL vout; namespace Trie{ int MX[M],MN[M],ch[M][SGZ],cnt,root,NUM,COL,ans_tmp; inline void init(){ memset(MX,-1,sizeof(MX)); memset(MN,-1,sizeof(MN)); memset(ch,0,sizeof(ch)); cnt = root = 0; } void Insert(int &w, int t){ if (!w) w = ++cnt; if (!~MX[w] || MX[w] < COL) MX[w] = COL; if (!~MN[w] || MN[w] > COL) MN[w] = COL; if (t) Insert(ch[w][(NUM&t)>0],t>>1); } inline void insert(int num, int col){ if (!root) root = ++cnt; NUM = num, COL = col; Insert(ch[root][(num&(1<<30))>0],1<<29); } void Query(int w, int t){ if (t) { int to = ch[w][((NUM&t)>0)^1]; if (to && (MX[to] != COL || MN[to] != COL)) ans_tmp |= t, Query(to,t>>1); else Query(ch[w][(NUM&t)>0],t>>1); } else { if (COL != MN[w]) COL = MN[w]; else COL = MX[w]; } } inline pair<int,int> query(int num, int col){ ans_tmp = 0; NUM = num; COL = col; Query(root,1<<30); return make_pair(ans_tmp,COL); } }; inline int find(int w){ int f=fa[w],tmp; while (fa[f] != f) f = fa[f]; while (w != f) tmp = fa[w], fa[w] = f, w = tmp; return f; } inline int read(){ char c=getchar(); int ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); return ret; } int main(){ n = read(); int cnt = n-1; for (int i=1;i<=n;i++) arr[i] = read(), fa[i] = i; while (cnt) { Trie::init(); memset(val,0,sizeof(val)); for (int i=1;i<=n;i++) Trie::insert(arr[i],find(i)); for (int i=1;i<=n;i++) { pair<int,int> tmp = Trie::query(arr[i],fa[i]); if (tmp.first > val[fa[i]]) val[fa[i]] = tmp.first, to[fa[i]] = tmp.second; } for (int i=1;i<=n;i++) if (to[i] && find(to[i]) != find(i)) vout += val[i], fa[find(i)] = find(to[i]), cnt--; } printf("%lld\n",vout); return 0; }
不过貌似这个题直接暴力就行了?