重剑无锋
我生待明日,万事成蹉跎
posts - 13,  comments - 6,  trackbacks - 0
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 阅读(419) 评论(0)  编辑 收藏 引用 所属分类: Data Structure

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿

随笔分类

随笔档案

friends

  • figoSB
  • 除了我...谁敢叫韩飞sb...

搜索

  •  

最新评论

阅读排行榜

评论排行榜