杭电3234——带权并差集（异或运算）

杭电3234——带权并差集（异或运算）

杭电3234传送门

写在题前：

• 拿到题的时候，woc，这是个什么鬼题哦！
• 刚开始不知道异或的一些运算，所以没怎么有思路，后来找了异或公式，还是没怎么有思路，哈哈哈。
• 有用的异或公式：a ^ b ^ b ^ c ^ b ^ c ^ b ^ c = a ^ c 。（就是可以消去两个相同的元素，有点消消乐的感觉）
• 可以搜一下异或运算的应用，比如说：判断重复元素等等。还是挺有意思的。

解题思路：

带权并差集：权值就是两个节点的异或值。

1. 判断需要进行的操作
2. I p v ：就把 p 和虚拟节点n建立联系（如果这个集合里面有n，说明这个集合能计算出具体的异或值）。
3. I p q v ：把 p 和 q 建立联系，权值为v
4. Q 操作：进行查询。

具体见代码解析：

写在题后：

• 这题有坑，这题有坑，这题有坑！！！重要事情说三遍。输入多组样例，每组样例之间用空行隔开，最后一个样例也有空行！，但是呢，题中给的样例输出就没有空行，你说气不气。
• 这个题难度还行，就是感觉这个操作的过程太复杂了，好好捋一捋，转过这个弯之后，还算挺好做的！

ac代码

# include <iostream>
# include <algorithm>
# include <cstdio>
# include <cstdlib>
# include <string>
# include <cstring>
# include <vector>
# include <map>
using namespace std;
typedef long long ll;const int maxn = 20010;
int id[maxn];//记录父亲节点
int weight[maxn];//记录和父亲节点的异或值（权值）
int num[maxn];//记录需要查询的节点集合
int m, n;int fin(int x) {//寻找x节点最上面的父亲节点if (x != id[x]) {int t = id[x];id[x] = fin(id[x]);weight[x] ^= weight[t];//路径压缩的同时，更新权值，}return id[x];
}bool meg(int u, int v, int w) {// u 和 v 建立连接，权值为 w，返回能否建立连接int a = fin(u);//u最上面的父亲节点int b = fin(v);//v最上面的父亲节点if (a == b) {//如果 u、v 已经有关系if ((weight[u] ^ weight[v]) != w) {//判断输入的数据是否有逻辑错误return false;//有错误，返回false}else {return true;//没有错误，返回true}}if (a == n) {//这个if语句非常重要，非常重要，非常重要。//如果a是虚拟节点的时候，a 和 b 相互交换。//目的：保证a永远不是不是虚拟节点，保证虚拟节点是最上面的节点。a = b;b = n;}id[a] = b;// a、b 建立连接weight[a] = weight[u] ^ weight[v] ^ w;//更新权值，公式解释见图1return true;
}int main() {int Ti = 1;while (cin >> n >> m) {if (n == 0 && m == 0) {break;}cout << "Case " << Ti++ << ":" << endl;for (int i = 0; i < n + 10; i++) {id[i] = i;}memset(weight, 0, sizeof(weight));//初始化bool Return = false;//记录是否有错误的输入int cnt = 0;//记录 i 操作的个数while (m--) {string str;cin >> str;if (str[0] == 'I') {cnt++;string anw;getline(cin, anw);anw.push_back(' ');int u, v, w;int k = 0;vector<int>kt;for (int i = 1; i < anw.size(); i++) {if (anw[i] == ' ') {kt.push_back(k);k = 0;}else {k = k * 10 + anw[i] - '0';}}if (kt.size() == 2) {u = kt[0];v = n;w = kt[1];}else if (kt.size() == 3) {u = kt[0];v = kt[1];w = kt[2];}if (Return) {continue;}//以上是将 i 操作的数字放进 u、v、w 里面的操作（还可以用c里面的sscanf来操作，可能会简单一点）//如果只有 i 后面只有两个数字，v的值就是n。if (!meg(u, v, w)) {//如果不能建立连接，以后的操作都不考虑cout << "The first " << cnt << " facts are conflicting." << endl;Return = true;}}else if(str[0]=='Q'){int K;cin >> K;for (int i = 0; i < K; i++) {cin >> num[i];//把需要查询的节点放进 num 数组里}if (Return) {continue;}int ans = 0;//记录查询节点之间的异或值bool vis[maxn];//记录查询的节点是否被访问memset(vis, false, sizeof(vis));for (int i = 0; i < K; i++) {if (vis[i]) {//如果节点已经被访问，就无需访问continue;}int len = 0;//记录查询的的节点的个数//如果是奇数，就不可能算出答案//如果是偶数，就可以算出答案int froot = fin(num[i]);for (int j = i; j < K; j++) {if (vis[j]==false && fin(num[j]) == froot) {//如果 j 节点没有被访问过，i 和 j 属于同一个集合//就将 j 节点放进 ans 里。len++;vis[j] = true;ans ^= weight[num[j]];}}if (froot != n && len % 2 == 1) {//如果这个集合里面没有虚拟节点 n 而且集合元素个数是奇数//那么一定不能算出异或值。返回-1.ans = -1;break;}//关于能计算出来异或值的情况有两种，只要满足一种就能计算出集合元素之间的异或值//1、如果集合里面有虚拟节点 n ，说明集合里面有一个节点的值是知道的，通过他们之间的异或关系，能知道所有节点的值，集合元素之间的异或值也能计算出来。见图2//2、如果集合里面节点的个数是偶数个，就可以通过异或的性质来计算出集合的异或值。因为ans记录的是集合每个元素和其父亲节点之间的异或值，偶数个的话，能把父亲节点消了了，见图3、4。}if (ans == -1) {cout << "I don't know."<<endl;}else {cout << ans << endl;}}}cout << endl;//注意每个样例后面都有一个空行。}return 0;
}

代码中图片

图1

图2

图3

图4