396 E

AtCoder Beginner Contest 396 - AtCoder

思路：

因为重点是要求的是 \(min(\sum\limits_{i = 0}^n a_i)\)，所以对于题目给的 \(X_i, Y_i, Z_i\)， 我们可以直接将 \(X_i, Y_i\) 看成是给定的数组 \(a\) 的下标

那么我们将题目转换一下：

对于给定的 \(m\) 组数据，每组数据给定数组 \(a\) 的下标 \(i\) 和下标 \(j\) 以及 \(a[i]\) 和\(a[j]\) 的异或值，要求确定数组 \(a\)，要求 \(min(\sum\limits_{i = 0}^n a_i)\)

因为给定的数据可能相互之间矛盾，所以我们利用并查集来维护各个节点到根节点的距离（根节点的选择是任意的）

例如：对于数据

1
2
3
4
5
4 4
1 3 4
1 2 3
2 4 5
2 3 5

我们可以画出如下图示：

可以看出因为节点 \(a[1]\) 和节点 \(a[2]\) 之间的距离有矛盾，所以输出-1

接着解决 \(min(\sum\limits_{i = 0}^n a_i)\) 的问题：

因为当根节点和距离确定了，那么与根节点相连的那个节点也可以确定，所以只需要判断根节点的大小即可

因为要求和最小，所以我们可以统计所有距离的二进制形式的每一位上的1的个数，如果1的个数大于一半，那么当根节点是1的时候，会有一半以上的节点该位是0，实现该位的最小；同理，如果1的个数小于等于一半，那么当根节点是0的时候，会有一半以上的节点该为是0，实现该为的最小

实现过程：

  1. 写一个带权并查集，将所有节点都路径压缩到根节点，判断是否有矛盾
    • 如果两个节点的根节点不同，就直接相连，并更改路径长度
    • 如果两个节点的根节点相同，就判断是否有矛盾
  2. 需要注意，图可能并不连通理有多个集合的情况；依次处理每一个连通块
  3. 根节点的异或值可能不等于0，所以需要处理！！！！例如可以给3 3 3吗，那么当节点3是根节点的时候，根节点的异或值是3
  4. 将所有路径上的长度的每一个二进制位的1的个数进行统计，使用数组vector<int> ct(32)，进行计数，判断1和 \(\lfloor \frac{n - 1}{2}\rfloor\) 的大小
    • \(n - 1\) 是因为剔除了根节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int f[N], d[N];
int find(int x)
{
	if(x != f[x])
	{
		int t = f[x];
		f[x] = find(f[x]);
		d[x] ^= d[t];
	}
	return f[x];
}
bool merge(int x, int y, int z)
{
	int fx = find(x), fy = find(y);
	if(fx != fy) 
	{
		f[fy] = fx;
		d[fy] = d[x] ^ d[y] ^ z;
		return true;
	}
	else return (d[x] ^ z) == d[y];
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) f[i] = i;
	int flag = 0;
	for(int i = 0; i < m; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		if(!merge(x, y, z))	flag = 1;
	} 
	if(flag)
	{
		cout << -1;
		return 0;
	}
	
	vector<vector<int>> g(n + 1);
	vector<int> ans(n + 1);
	
	for(int i = 1; i <= n; i++)//区分每一个连通块 
		g[find(i)].push_back(i);
	
	for(auto u: g)//读取每一个连通块 
	{
		if(u.empty()) continue;
		vector<int> count(32);
		for(auto i: u)
		{
			int t = d[i], cnt = 0;
			while(t)
			{
				count[cnt++] += t % 2;
				t /= 2;
			}
		}
		int root = 0;
		for(int i = 0; i < 32; i++)
			if(count[i] > u.size() - count[i]) root |= (1 << i);
		for(auto i: u) ans[i] = root ^ d[i];
	}
	for(int i = 1; i <= n; i++)	cout << ans[i] << " "; 
	return 0;
}