程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3234 異或（加權並查集）

hdu 3234 異或（加權並查集）

編輯：C++入門知識

hdu 3234 異或（加權並查集）

有n(n<=20000)個未知的整數X0,X1,X2Xn-1，有以下Q個(Q<=40000)操作：

I p v :告訴你Xp=v

I p q v :告訴你Xp Xor Xq=v

Q k p1 p2 … pk : 詢問 Xp1 Xor Xp2 .. Xor Xpk， k不大於15。

如果當前的I跟之前的有沖突的話，跳出

思路就是並查集的擴展，每個節點表示他與根結點的異或值。。。。思路略

ps：忘打了個.導致wa了好長時間............跪了

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
using namespace std;  
#define LL long long  

const LL maxn = 20000 + 5;
const LL INF = 1000000000;

LL x[maxn]; 
LL pa[maxn], num[maxn], n;//num數組記錄每個集合中的元素個數 

void init() {              //增加了一個xn，即零結點                       
	for(LL i = 0; i <= n; i++) { pa[i] = i; x[i] = 0;} 
}

LL find(LL id) {
	if(id != pa[id]) {
		LL tmp = pa[id];
		LL root = find(pa[id]);
		x[id] ^= x[tmp];
		return pa[id] = root; 
	}
	else return id;
}

bool unio(LL p, LL q, LL v) {
	LL pap = find(p), paq = find(q);
	if(pap == paq) {
		return (x[p] ^ x[q]) == v;        //注意運算符的順序，如果不加括號會錯，位運算一定要小心優先級 
	}
	if(pap == n) swap(pap, paq);
	pa[pap] = paq;
	x[pap] = x[p] ^ x[q] ^ v;   // 最重要的一步，將兩顆樹連接在一起，很巧妙； 
	return true; 
}

int main() {
	//freopen("input.txt", "r", stdin);
	LL Q, kase = 1;
	while(scanf("%lld%lld", &n, &Q) && n) {
		init(); 
		printf("Case %lld:\n", kase++);
		char cmd[2], str[20];
		LL facts = 0; bool flag = true;
		for(LL i = 1; i <= Q; i++) {
			if(!flag){ gets(str); continue;}
			scanf("%s", cmd); 
			if(cmd[0] == 'I') {
				facts++;
				gets(str);
				LL p, q, v;
				if(sscanf(str, "%lld%lld%lld", &p, &q, &v) == 2) {
					v = q; q = n;
				}
				if(!unio(p, q, v)) {
					printf("The first %lld facts are conflicting.\n", facts);
					flag = false;
					continue;	
				}
			}
			else {
				LL k, idp[20], tag = 1;
				LL ans = 0;
				scanf("%lld", &k);
				for(LL i = 0; i < k; i++) {
					scanf("%lld", &idp[i]);
					num[find(idp[i])] = 0;
				}
				for(LL i = 0; i < k; i++) {
					num[find(idp[i])]++;
					ans ^= x[idp[i]];
				}
				for(LL i = 0; i < k; i++) {
					if(num[find(idp[i])] % 2 == 1 && find(idp[i]) != n) {
						tag = 0; break;
					}
				}
				if(!tag) printf("I don't know.\n");
				else printf("%lld\n", ans);
			}
		}
		printf("\n");
	}
	return 0;
}