题意:有N个方块,M个操作{“C x”:查询方块x上的方块数;“M x y”:移动方块x所在的整个方块堆到方块y所在的整个方块堆之上}。输出相应的答案。
解法:带权并查集。每堆方块作为一个集合,维护3个数组:fa[x]表示x方块所在堆的最顶部的方块;d[x]表示x方块所在堆的最底部的方块;f[x]表示x方块方块x上的方块数。
注意——一般画树理解,这个图用方块理解好一点,例子:【bzoj 1202】[HNOI2005] 狡猾的商人(图论--带权并查集+前缀和) 。要想原本fy是恰好放在x所在联盟的最底部的点下面的,只是为了减少时间复杂度才把它提到为fx的子节点。因此式子仍因按原来的图形来写。
P.S.这个虽然是我做的第一道题,但我搞错了,这不是最佳的模版题!见:【poj 1962】Corporative Network(图论--带权并查集 模版题)
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6
7 const int N=30010,M=100010;
8 int fa[N],f[N],d[N];
9 char s[3];
10
11 int ffind(int x)
12 {//查找+更新 关于x的所有值
13 if (fa[x]!=x)
14 {
15 int fx=fa[x];
16 fa[x]=ffind(fx);
17 f[x]+=f[fx];
18 d[x]=d[fx];
19 }
20 return fa[x];
21 }
22 int main()
23 {
24 int n,m,x,y;
25 scanf("%d",&m);
26 for (int i=1;i<=N-10;i++) fa[i]=d[i]=i,f[i]=0;
27 while (m--)
28 {
29 scanf("%s",s);
30 if (s[0]=='M')
31 {
32 scanf("%d%d",&x,&y);
33 int fx=ffind(x),fy=ffind(y);//无论如何,将x,y转化为fx和fy来操作,x,y不需要现在就更新完
34 fa[fy]=fx;//mainly 修改fy
35 ffind(d[fx]);//更新了之后才可用
36 f[fy]=f[d[fx]]+1;//画树理解时,要想原本fy是恰好放在d[fx]下面的,只是为了减少时间复杂度所以把它提到为fx的子节点
37 d[fx]=d[fy];//修改fx
38 }
39 else
40 {
41 scanf("%d",&x);
42 int dx=d[ffind(x)];
43 ffind(dx);//更新了才有保障
44 printf("%d\n",f[dx]-f[x]);
45 }
46 }
47 return 0;
48 }