B. Bitwise Exclusive-OR Sequence
我们考虑一种构造方式就是
让一个点为0 然后连接他的就一直异或上他连接的目标
这样虽然不能符合题意 达到最小但是 我们可以发现这个如果出现环的话
就会有冲突 我们必须让这个环的异或和为0 才是合法的
然后我们考虑如何去最小值
我们发现如果一个变的话 必须整体全都变才行
我们直接按位考虑即可
注意的是 要是不是一个连通块 显然我们可以分开来算
int n,m,st[N],ans,val[N];
vector<pair<int,int>>g[N];
vector<int>a;
void dfs(int u,int x){
st[u]=1;
val[u]=x;
a.push_back(x);
for(auto [v,w]:g[u]){
if(st[v]){
if((x^val[v])!=w){
cout<<-1<<endl;
exit(0);
}
continue;
}
dfs(v, x^w);
}
}
void solve(){
cin>>n>>m;
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});
}
for(int i=1;i<=n;i++){
if(!st[i]){
a.clear();
dfs(i,0);//black
for(int k=0;k<30;k++){
int cnt=0;
for(auto j:a)
if(j>>k&1)cnt++;
ans+=min((int)a.size()-cnt,cnt)*(1<<k);
}
}
}
cout<<ans<<endl;
}
标签:cnt,Regional,val,Contest,int,Shenyang,back,st,push
From: https://www.cnblogs.com/ycllz/p/16887024.html