MinOr Tree

发表于 分类于 ，

    给定 $n$ 个点 ， $m$ 条边 $(3 \le n \le 2 \times 10^5,n - 1 \le m \ \le 2 \times 10^5)$ , 求在或运算下的最小生成树。

    保证图联通。

MinOr Tree

Created by LXC on Sun Jan 14 11:42:41 2024

https://codeforces.com/problemset/problem/1624/G

ranting: 1900

tag: bitmasks, dfs and similar, dsu, graphs, greedy

problem

给定 $n$ 个点 ， $m$ 条边 $(3 \le n \le 2 \times 10^5,n - 1 \le m \ \le 2 \times 10^5)$ , 求在或运算下的最小生成树。

保证图联通。

solution

从高位i开始贪心，检查第i位为0的所有边集合能否生成树。如果不能则将第i位必为1，如果能则可以在第i位为0的所有边集合中进一步缩小范围，检查第i-1位为0边权集合是否能生成树。依次类推。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

int x[N], y[N], w[N];

struct Dsu {
    vector<ll> fa;
    Dsu(int sz) : fa(sz, -1) {}

    int find(int u) {
        return fa[u] < 0 ? u : fa[u] = find(fa[u]);  // 路径压缩
    }

    void unite(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            // 小集合fu 加入到 大集合fv，按秩归并
            if (fa[fu] < fa[fv])
                swap(fu, fv);
            fa[fv] += fa[fu];
            fa[fu] = fv;
        }
    }
};

void sol() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i] >> w[i];
    }
    auto check = [&](int msk) {
        Dsu dsu(n + 1);
        for (int i = 1; i <= m; i++) {
            if ((w[i] | msk) == msk) {
                dsu.unite(x[i], y[i]);
            }
        }
        int neg = 0;
        for (int i = 1; i <= n; i++) {
            if (dsu.fa[i] < 0)
                neg++;
        }
        return neg == 1;  // 只有一个根，可以生成树
    };
    int mask = (1 << 30) - 1;
    for (int i = 29; i >= 0; i--) {
        if (check(mask ^ (1 << i)))
            mask ^= (1 << i);
    }
    cout << mask << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}