拓展域

拓展域,个人感觉算是并查集中比较难的部分了。(网上都没什么详细的教学。。。全靠理解代码

简而言之,就是用多个并查集,多个空间,来表示节点之间的一些相互关系,比如x的敌人,x的朋友,我需要找到x的敌人的敌人,就也是我的朋友,x的敌人的朋友,就也是我的敌人。(【NOIP 2010 提高组】关押罪犯)

不多说,直接看例题吧。

(我感觉我说肯定说不清楚。。。

例题解释

1、POJ-1182 食物链

题目大意就是,告诉你一些动物之间的关系(同类或者捕食),如果满足这三个条件

1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话;

就是假话。问你假话的数量。

我们可以用在同一个并查集的表示是同一类,x+n表示捕食关系。

x->x+n->x+2*n->x

如果x和y是同类,那么

1) x和y是同一类;
2) x+n和y+n是同一类;
3) x+2 * n和y+2 * n是同一类;

如果x和y是捕食关系,那么

1) x和y+2 * n是同一类;
2) x+n和y是同一类;
3) x+2 * n和y+n是同一类;

这样就可以用三个并查集来表达之间的关系了。

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
#include <iostream>
using namespace std;

const int N = 5e4 + 5;
int f[3 * N + 5];

int find(int root) {
int son = root, t;
while (root != f[root]) root = f[root];
while (son != root) {
t = f[son];
f[son] = root;
son = t;
}
return root;
}

void join(int root1,int root2) {
root1 = find(root1);
root2 = find(root2);
if (root1 != root2) f[root1] = root2;
}

int main() {
int n, k;
scanf("%d %d", &n, &k);
for (int i = 1; i <=3*n; i++) {//初始化,三倍空间
f[i] = i;
}
int ans = 0;
int d, x, y;
while (k--) {
scanf("%d %d %d", &d, &x, &y);
if (x > n || y > n) {//大于n就是假话,直接continue
ans++;
continue;
}
if (d == 1) {
if (find(x + n) == find(y) || find(x) == find(y + n)) ans++;
//x捕食y或者y捕食x,关系不符,就是假话
else {
join(x, y);
join(x + n, y + n);
join(x + 2 * n, y + 2 * n);
}
}
else {
if (find(x) == find(y) || find(y + n) == find(x)) ans++;
//x和y是同一类或者y捕食x,关系不符,就是假话
else {
join(x + n, y);
join(x + 2 * n, y + n);
join(x, y + 2 * n);
}
}
}
printf("%d\n", ans);
}

2、POJ-1733 Parity game

你有一串由0和1构成的序列,告诉你一些关系([L,R]中1的个数是奇或偶),问你哪个地方出现了矛盾,输出最早出现矛盾的位置。

(这个题目。。相当头疼,想了好久,根本看不懂,我也不确定我能解释清楚。。

首先要离散化,n太大了,数组放不下,需要先离散化。

然后我们可以用d[x]表示x到根节点之间是奇是偶,用f[x](并查集)表示前后关系。

如果根节点相同的时候,就需要判断是否矛盾。判断矛盾的时候可以用

d[x]^d[y] 表示x到y之间的1的个数

1) d[x] = 0,d[y] = 0 时,d[x]-d[y] == d[x]^d[y] == 0;
2) d[x] = 0,d[y] = 1 时,d[x]-d[y] == d[x]^d[y] == 1;
3) d[x] = 1,d[y] = 0 时,d[x]-d[y] == d[x]^d[y] == 1;
4) d[x] = 1,d[y] = 1 时,d[x]-d[y] == d[x]^d[y] == 0;

在路径压缩上,也可以使用同样的方法

d[x]^d[f[x]] 表示x到f[x]之间的1的个数(用递归来实现)

1) d[x] = 0,d[y] = 0 时,d[x]+d[y] == d[x]^d[y] == 0;
2) d[x] = 0,d[y] = 1 时,d[x]+d[y] == d[x]^d[y] == 1;
3) d[x] = 1,d[y] = 0 时,d[x]+d[y] == d[x]^d[y] == 1;
4) d[x] = 1,d[y] = 1 时,d[x]+d[y] == d[x]^d[y] == 0;

关系表示完后,即可写出正确代码。

(。。。我觉得没那么简单,我是真的菜。。根本想不到的好吧

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
#include <iostream>
#include <map>
using namespace std;

const int N = 5050;
int f[2 * N], d[2 * N];
map<int, int> num;//n太大了,不能用数组

int search(int root) {
if(root != f[root]) {
int t = search(f[root]);//递归寻找根节点
d[root] = d[root] ^ d[f[root]];//更新d[x]的值
f[root] = t;
}
return f[root];
}

int join(int x, int y, int l) {
int rx = search(x);
int ry = search(y);
if (rx == ry) {
if ((d[x] ^ d[y]) != l) return 0;//判断是否矛盾
else return 1;
}
else {
f[ry] = rx;
d[ry] = (d[x] + d[y] + l) % 2;
//d[ry] = (d[x] ^ d[y] + l) % 2;也可
}
return 1;
}

int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= 2 * N - 5; i++) {
f[i] = i;
}
int cnt = 1, mark = 0;
for (int i = 1; i <= m; i++) {
int x, y, l;
char ch[10];
cin >> x >> y >> ch;
if (!num[x - 1]) num[x - 1] = cnt++;//离散化
if (!num[y]) num[y] = cnt++;
if (ch[0] == 'e') l = 0;
else l = 1;
if (!join(num[x - 1], num[y], l)) {
mark = i;
break;
}
}
if (!mark) mark = m + 1;//如果没有冲突,就输出m
cout << mark - 1 << endl;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信