G. MinOr Tree
看到或运算 我们思考如何按位来做
我们可以贪心的 从高位到低位的 要是该位可以都用0的来构成一颗生成树 我们显然是很高兴的
但是怎么check?
我们每次遍历一次边 要是满足要求:
1.该位是0
2.不是处于同一个连通块
这样子写出来 发现过不了第三个样例
我们发现还有第三个要求就是:
3.当前边权w不能有我们前面已经确定了是0的位上w是1 这样显然悖论了
所以我们还要一个条件就是ans|w == ans
int n,m,p[N],ans;
vector<pair<int,int>>g[N];
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
void merge(int x, int y){
p[find(x)] = find(y);
}
bool check(int x){
for(int i=1;i<=n;i++)p[i]=i;
for(int i=1;i<=n;i++)
for(auto [v,w]:g[i])
if((w>>x&1)==0&&find(i)!=find(v)&&(w|ans)==ans)
merge(i,v);
for(int i=1;i<=n;i++)if(find(1)!=find(i))return false;
return true;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)g[i].clear(),p[i]=i;
for(int i=1;i<=m;i++){
int u,v,w;cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
ans=2147483647;
for(int i=30;i>=0;i--)
if(check(i))ans-=(1<<i);
cout<<ans<<endl;
}
标签:back,int,Codeforces,764,check,ans,Div,find
From: https://www.cnblogs.com/ycllz/p/16859037.html