Graph

思路

圖是聯通的，并且加邊的時候要保證環一定是異或值為0，所以我們可以保證從一個點到另一個點的路徑異或值是不變的，這個時候就簡單了，不就是一個異或最小生成樹了嘛。

我們只要預處理一下，任選一個點作為根節點去得到從這個點到其他點的路徑異或值，然后再做一遍異或最小生成樹即可。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h>#define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int N = 1e5 + 10;int trie[N * 30][2], tot, a[N];int head[N], to[N << 1], nex[N << 1], value[N << 1], cnt = 1;void add(int x, int y, int w) {to[cnt] = y;nex[cnt] = head[x];value[cnt] = w;head[x] = cnt++; }void insert(int x) {int rt = 0;for(int i = 29; i >= 0; i--) {int now = x >> i & 1;if(!trie[rt][now]) {trie[rt][now] = ++tot;rt = trie[rt][now];trie[rt][0] = trie[rt][1] = 0;}else {rt = trie[rt][now];}} }int find(int x) {int ans = 0, rt = 0;for(int i = 29; i >= 0; i--) {int now = x >> i & 1;if(trie[rt][now]) {rt = trie[rt][now];}else {ans |= 1 << i;rt = trie[rt][now ^ 1];}}return ans; }ll ans = 0;void dfs1(int l, int r, int dep) {if(dep < 0 || l >= r) return ;int mid = l - 1;while(mid < r && ((a[mid + 1] >> dep) & 1) == 0) mid++;dfs1(l, mid, dep - 1);dfs1(mid + 1, r, dep - 1);if(mid == l - 1 || mid == r) return ;tot = 0, trie[tot][1] = trie[tot][0] = 0;for(int i = l; i <= mid; i++) {insert(a[i]);}int now = INT_MAX;for(int i = mid + 1; i <= r; i++) {now = min(now, find(a[i]));}ans += now; }void dfs2(int rt, int fa, int w) {a[rt] = w;for(int i = head[rt]; i; i = nex[i]) {if(to[i] == fa) continue;dfs2(to[i], rt, w ^ value[i]);} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int n = read();for(int i = 1; i < n; i++) {int x = read(), y = read(), w = read();add(x, y, w);add(y, x, w);}dfs2(1, 0, 0);sort(a, a + n);dfs1(0, n - 1, 29);printf("%lld\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的BGraph（异或最小生成树）的全部內容，希望文章能夠幫你解決所遇到的問題。

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