http://poj.org/problem?id=1988这个题和我之前做的题目都不太一样,这里是很多个小的集合,这个也更像一个并查集,只不过我原来不知道,原来很多个集合也可以维护和爸爸的关系,也终于明白为什么figo觉得 食物链那个并查集是水题了. 一个数组维护的是父节点(基本并查集), 还有一个v数组,是用来记录一个节点的值,这个值有这样的特点:计算本节点的值是下面的节点在并查集中是上面的节点的值+本节点的v. 意思就是说,要算x点到栈底有多远,就要x的父亲离栈底有多远+x离父亲有多远,所有的并查集都是维护和父亲的关系,我想了很久刚开始想错了方向. 记住:并查集是维护和父亲的关系的. 这道题还有一关,就是 合并两个集合的时候要注意,一定要清楚加入到另一个节点下的树(叫新树),的值是多少,这个很好想,就是有东西放到了新树的下面,所以新树的根值就是原来那颗树里面的元素个数,所以还有一个数组,维护每一个集合的元素数目的num,最后一部在合并的时候,要把整个集合的元素数目 = 旧树+新树 (元素数目) 更新了. 然后路径压缩很简单,一直加值,自己的+父亲的,直到根为止.
代码如下:
code:
1 #include<iostream> 2 #include<cstdio>
3 using namespace std;
4 #define REP(i,from,to) for(int i=(from);i<=(to);++i)
5 const int N = 30002;
6 int a[N],v[N],num[N];
7 struct disset{
8 int *d,*v,*num,l;
9 disset(int *d,int *v,int* num,int l):d(d),v(v),num(num),l(l){
10 REP(i,1,l){
11 d[i]=i;
12 v[i]=0;
13 num[i]=1;
14 }
15 }
16 int find(int x){
17 int u = d[x];
18 if(u!=x){
19 d[x] = find(u);
20 v[x] += v[u];
21 }
22 return d[x];
23 }
24 void add(int x,int y){
25 int ux = d[x];
26 int uy = d[y];
27 d[ux] = uy;
28 v[ux] = num[uy];
29 num[uy] += num[ux];
30 }
31 int getv(int x){
32 return v[x];
33 }
34 }*s;
35 int work(char c,int x,int y){
36 int ux = s->find(x);
37 int uy = s->find(y);
38 if(c=='M'){
39 if(ux!=uy)
40 s->add(x,y);
41 }
42 else{
43 return s->getv(x);
44 }
45 return -1;
46 }
47 int main(){
48 int tcase;
49 while(scanf("%d",&tcase)!=EOF){
50 s = new struct disset(a,v,num,N-2);
51 while(tcase--){
52 char c[2];
53 int x,y=-1,ans;
54 scanf("%s",c);
55 if(c[0]=='M')
56 scanf("%d%d",&x,&y);
57 else
58 scanf("%d",&x);
59 ans=work(c[0],x,y);
60 // REP(i,1,6)
61 // cout<<a[i]<<' '<<v[i]<<'|';
62 // cout<<endl;
63 if(ans!=-1)
64 printf("%d\n",ans);
65 }
66 delete s;
67 }
68 return 0;
69 }
posted on 2012-07-11 00:46
Gin 阅读(409)
评论(0) 编辑 收藏 引用 所属分类:
Data Structure