第 46 届 ICPC 区域赛（沈阳）B-Bitwise Exclusive-OR Sequence（异或环、二分图染色变种、贪心）

第 46 届 ICPC 区域赛（沈阳）B-Bitwise Exclusive-OR Sequence（异或环、二分图染色变种、贪心） 位异或序列

题意：

给定一个包含 n 个数的序列，再给出 m 条关系 —— 限制序列内两两数u、v 异或^ 得到的值为 w问这 m 条关系是否能同时成立且无矛盾，有矛盾输出-1，否则输出 这个序列 n 个数累加的最小值 使得关系成立无矛盾

思路：

根据异或的交换性我们可以得到：u ^ v == w 等 价 于 等价于 等价于 v = u ^ w分情况讨论：当异或关系不成环时，肯定不会发生冲突；否则，固定环上任意一点的值，通过交换性我们肯定能推导出它相连的另一个点的值，如此推导回初始点的位置判断下是否值相同即可判断有无解判断完有无解，对每个数的二进制状态观察分析我们拆分枚举 u 点的二进制位，对应位置下 w 的二进制位若是 1，证明 v 点该位的 “颜色”（01）应该与 u 不同，反之相同；通过这样染色，我们能枚举每一个01连通块，而且可以发现二进制每一位的关系都是互相独立互不干扰，所以对于任意连通块我们只需要取出两种颜色中最小的个数，位 b i t bit bit也知晓，所以累计 2 b i t 2^{bit} 2bit贡献即可

C o d e : Code: Code:

#include
#include
#include
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul (u << 1)
#define ur (u << 1 | 1)
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define rfor(a,b,c) for(int a=b;a>=c;a--)
//#define x first
//#define y second
//[博客地址](https://blog.csdn.net/weixin_51797626?t=1) 
using namespace std;

typedef long long ll;
typedef pair PII;
typedef unsigned long long ull;

const int N = 100010, M = 400010, MM = N;
int INF = 0x3f3f3f3f, mod = 1e9 + 7;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
int h[N], e[M], ne[M], w[M], idx;
int color[N][30], vis[N];
int a0, a1;

inline void add(int a, int b, int x) {
	e[idx] = b, ne[idx] = h[a], w[idx] = x, h[a] = idx++;
}

void inline read(int& x) { //传入地址直接修改
	x = 0;
	int f = 1;//特判负数
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-')f = -1;//有负号即负数
		c = getchar();
	}
	while (c >= '0' && c <= '9')
		x = x * 10 + (c - '0'), c = getchar();
	x *= f;
}

void dfs(int x, int c) {
	vis[x] = c;
	for (int i = h[x]; ~i; i = ne[i]) {
		int j = e[i];
		if (vis[j] == -1)dfs(j, c ^ w[i]);//交换性，赋予下一个点权值
		else if ((vis[j] ^ c) != w[i]) {
			cout << -1;//若冲突
			exit(0);
		}
	}
}

void find(int x, int c, int bit) {
	color[x][bit] = c;
	if (c == 1)a0++;//统计两种颜色个数
	else a1++;

	for (int i = h[x]; ~i; i = ne[i]) {
		int j = e[i];
		if (!color[j][bit]) { //没染过
			if (w[i] >> bit & 1)//判断是否同色
				find(j, 3 - c, bit);
			else find(j, c, bit);
		}
	}
}

int main() {

	read(n), read(m);
	mem(h, -1);
	mem(vis, -1);//初始化每个点值为 -1

	forr(i, 1, m) {
		int a, b, x;
		read(a), read(b), read(x);
		add(a, b, x), add(b, a, x);//无向图
	}

	//第一次染色
	forr(i, 1, n)if (vis[i] == -1)dfs(i, 0);//每个点能染就判断是否成环无解

	ll ans = 0;
	forr(i, 1, n)
		//二次染色
		if (!color[i][0]) { //枚举每一个点的二进制位
			rfor(j, 29, 0) { //数据范围是2的{0-29}位
				a0 = a1 = 0;
				find(i, 1, j);
				ans += 1LL * min(a0, a1) * (1 << j);
			}
		}
	cout << ans;

	return 0;
}