第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳）B.Bitwise Exclusive-OR Sequence（二分图染色 + dfs）

题目链接：B-Bitwise Exclusive-OR Sequence_第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳） (nowcoder.com)

题意 / Problem

给定N个点，M条边，点权未知但是每条边上的边权就是其所连接的两个点的点权的异或和。问怎样规划点权可以使得所有点的点权加和最小，输出最小和。

注意：图不一定连通。（这个特别坑！！！）

思路 / Thought

将一个点的点权通过二进制位划分，我们知道不同位之间是相互独立的。又因为这个图未必连通，所以我们不妨假设有3块（举个例子），那么就先给第一块跑二分图，将其对结果的贡献加上，再将计数器清零，给第二块跑二分图.....以此类推，也就是说每个点都不能落下，而不同块之间也是相互独立的。

具体实现看代码，注意dfs时应该判断是否出现矛盾，如果有矛盾直接返回-1，结束程序。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
struct Edge{int x, w;};
vector<Edge> g[maxn];
int N, M, cnt[2], col[maxn];

bool dfs(int x,int i,int o)//o表示color 
{
	col[x] = o, cnt[o] ++;
	bool res = true;
	for(auto &j : g[x])
	{
		int y = j.x, w = j.w;
		if(col[y] != -1)
		{
			//注意这里的col[x]和col[y]表示的不是权值
			//而是一个0或1，所以要把w向右移动i位做异或判断是否为0
			//如果不为0说明产生了矛盾 
			if(col[x] ^ col[y] ^ (w >> i & 1))return false;//出现矛盾 
			continue;//已经走过 
		}
		//res将所有递归的子结果做且运算 
		if(w >> i & 1)res = res && dfs(y, i, o ^ 1);
		else res = res && dfs(y, i, o);
		
		if(!res)break;
	}
	return res;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> M;
	while(M --)
	{
		int u, v, w;cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	
	int sum = 0;
	bool tag = true;//表示答案合法 
	
	for(int i = 0;i < 30 && tag; ++ i)//考虑第i位 
	{
		memset(col, -1, sizeof col);
		for(int j = 1;j <= N; ++ j)
		{
			cnt[0] = cnt[1] = 0;//计数器清零，开始计算一个新的连通块 
			if(col[j] != -1)continue;//如果某个点已经被计算过，直接跳过 
			tag = tag && dfs(j, i, 0);//计算新的连通块大小，更新cnt[0]和[1] 
			sum += min(cnt[0], cnt[1]) << i;
		}
	}
	cout << (tag ? sum : -1) << '\n';
	
	return 0;
}