Codeforces Round #764 (Div. 3) 补 G. MinOr Tree 最小或树

题目大意

给定一棵 n n n个点 m m m条边的图，要求求图的最小或生成树(生成树的边权或和最小)

思路

首先求或的最小值，那么让高位尽可能的为 0 0 0。那么可以从高位开始枚举每一位，对每一位再枚举每条边，判断只选取此位为 0 0 0的边能否形成一棵树；如果能构成，最终结果的二进制该位肯定也为 0 0 0，此位为 1 1 1的边全部舍弃，在之后的枚举中不会使用；如果不能构成，该位直接抛弃，检查下一位

Accepted Code

#include
using namespace std;

const int N = 2e5 + 10, M = 5e5 + 10;

int n, m, ans;
bool vis[N];
struct edge{
    int u, v, w;
    edge(int uu, int vv, int ww): u(uu), v(vv), w(ww) {}
    edge() {}
}edges[M];

vector sto;

int fa[N];

int find(int x){ return x ^ fa[x] ? fa[x] = find(fa[x]) : x; }

inline bool judge(int x){
    sto.clear();
    for(int i = 1; i  x & 1){
            sto.push_back(i);
            continue;
        }
        int uu = find(u), vv = find(v);
        if(uu ^ vv) fa[uu] = vv, cnt++;
    }
    if(cnt == n - 1) return true;
    return false;
}

inline void solve(){
    cin >> n >> m;
    ans = (1 > v >> w;
        edges[i] = edge(u, v, w);
    }
    for(int i = 30; i >= 0; i--){
        if(judge(i)){
            for(auto t : sto) vis[t] = true;
            ans -= 1