G. MinOr Tree

G. MinOr Tree

1）题目大意：

n点m条边，做一颗生成树，使所有边的or结果最小。

2）思路：

没什么想法，请教大佬阿伟时候小悟了一波。

先将所有边放入集合。从高位到低位枚举二进制位。

1）如果可以用集合内的该二进制位为0的边构造出一个连通的图，那么答案中就不用加该二进制位。

并且在遍历完边后要将没有用到的边移出集合。（这就是为什么不是去构造一棵树，而是构造一个图。最后集合中留下的是最小的可以构建出最小或树的图）

2）如果构造不出来，那么就是说必须要用该二进制位为1的边，答案就需要加上该二进制位。

3）代码：

ll n , m ; 
ll fa[N] , vis[N] ;
struct edge{
	ll u , v , w ;
	bool usin ;
}eg[N] ;

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

void solve(){
	ll ans = 0 ;
	cin >> n >> m ;
	
	for(int i = 1 ; i <= n ; i ++ ) fa[i] = i ;
	
	for(int i = 1 ; i <= m ; i ++ ){
		cin >> eg[i].u >> eg[i].v >> eg[i].w ;
		eg[i].usin = 1 ;
	}
	
	for(int i = 30 ; i >= 1 ; i -- ){
		for(int j = 1 ; j <= n ; j ++ )fa[j] = j ;
		for(int j = 1 ; j <= m ; j ++ )vis[j] = 0 ;
		ll num = n ;

		for(int j = 1 ; j <= m ; j ++ ){
			//cout << (eg[j].w & (1LL << i)) << "<\n" ;
			if(!eg[j].usin || (eg[j].w & (1LL << (i - 1))) != 0) continue ;
			vis[j] = 1 ;
			ll fu = find(eg[j].u) ;
			ll fv = find(eg[j].v) ;
			if(fu != fv){
				num -- ;
				fa[fu] = fv ;
			}
		}
		//show1(fa , n) ;
		if(num != 1) ans += (1LL << (i - 1)) ;
		else{//可以用构造出0树 
			for(int j = 1 ; j <= m ; j ++ )
				if(!vis[j])eg[j].usin = 0 ; 
		}
		//cout << "i=" << i << ",num=" << num << " " << ans << "\n" ;
	}
	cout << ans << "\n" ;
}

4）附上大佬代码：

jiangly nb！！！