本文主要是介绍uva 12232 - Exclusive-OR(加权并查集),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:uva 12232 - Exclusive-OR
题目大意:有n个数,一开始并不知道具体的值,现在进行Q次操作。
- I u k:au的值为k
- I u v k:au⨁av=k
- Q k q1q2…qk:求q1⨁q2…⨁qk
对于Q操作不能确定的话输出"I don't know."
对于I操作矛盾的话则输出是第几条I操作出现矛盾的,并且停止后面所有的操作。
解题思路:加权并查集,f[x]表示x节点父亲节点,d[x]表示x节点与其父节点的亦或值,对于确定的节点值,可以将父亲节点设为0,这样的话在合并操作的时候就要注意,如果有一段0是父亲节点的话,就要将令一个节点指向0节点(也就是说0节点是固定不能有父亲节点的),一是在指向0节点的联通集合是确定值的,在查询是需要特判,二是进行第一种操作的时候方便处理。
在查询时,需要将所有的数分成各个联通集合,如果存在联通集合的个数为奇数,并且根节点不为0的话就是不能确定值的,否则取所有节点与父亲节点的亦或值的亦或和即可。
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 20005;
const int maxm = 105;bool flag;
int N, Q, f[maxn], d[maxn];int getfar (int x) {if (x == f[x])return x;int tmp = f[x];f[x] = getfar(f[x]);d[x] ^= d[tmp];return f[x];
}void query () {int n, ret = 0, num[maxm], vis[maxm];memset(vis, 0, sizeof(vis));scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &num[i]);num[i]++;}if (flag)return;for (int i = 0; i < n; i++) {int root = getfar(num[i]), cnt = 1;if (root == 0 || vis[i])continue;for (int j = i+1; j < n; j++) {if (getfar(num[j]) == root) {cnt++;vis[j] = 1;}}if (cnt&1) {printf("I don't know.\n");return ;}}for (int i = 0; i < n; i++)ret ^= d[num[i]];printf("%d\n", ret);
}bool link () {char s[maxm];gets(s);int u, v, k;int type = sscanf(s, "%d%d%d", &u, &v, &k);u++;if (type == 2) {k = v;v = 0;} elsev++;int p = getfar(u);int q = getfar(v);if (p == 0)swap(p, q);if (p != q) {f[p] = q;d[p] = d[u]^d[v]^k;} elsereturn (d[u]^d[v]) != k;return false;
}int main () {int cas = 1;while (~scanf("%d%d", &N, &Q) && N) {printf("Case %d:\n", cas++);flag = false;memset(d, 0, sizeof(d));for (int i = 0; i <= N; i++)f[i] = i;int ti = 0, u, v;char s[maxm];for (int i = 0; i < Q; i++) {scanf("%s", s);if (s[0] == 'I') {ti++;if (link()) {flag = true;printf("The first %d facts are conflicting.\n", ti);}} else if (s[0] == 'Q')query();}printf("\n");}return 0;
}
这篇关于uva 12232 - Exclusive-OR(加权并查集)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!