本文主要是介绍B Bitwise Exclusive-OR Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
给出n个顶点m条边，每条边<u,v,w> 代表点u异或点v的值为w，求解满足此规则的所有情况中，点之和最小值为多少?
解析
分层图，32位数字，我们分32位，对于每一层，我们可以先假定起点为1，如果按此遍历，我们自然可以得到所有点的情况，1的个数和0的个数是互补的，我们要让0尽可能地多,我们只要改变起点就能让0和1个数互换，当然，出现矛盾即是不可能，直接退出。我们统计每个连通分量所贡献的值。最后累加到我们的答案中即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
const int N=1e5+5,M=4e5+5;
int h[N],idx,v[N];
int e[M],ne[M],w[M];
ll CNT=0;
void add(int a,int b,int c){e[++idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx;
}
bool ed=0;
int dfs(int x,int d, int pre)
{int sum=1;if(ed)return 0;v[x]=pre;if(v[x]==1)CNT++;for(int i=h[x];i;i=ne[i]){int j=e[i];int quan=(w[i]>>d)&1;if(v[j]==-1){if(quan){sum+=dfs(j,d,pre^1);}else{sum+=dfs(j,d,pre);}}else{if((v[x]^v[j])!=quan){ed=1;return -1;}}}return sum;
}int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}ll res=0;for(int i=30;i>=0;i--){memset(v,-1,sizeof v);for(int j=1;j<=n;j++) {CNT = 0;//1;if (v[j] == -1) {ll ltk = dfs(j, i, 0);ll value = min(ltk - CNT, CNT);res += value * (1ll << i);if (ed) {printf("-1");return 0;}}}}printf("%lld",res);return 0;
}这篇关于B Bitwise Exclusive-OR Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
