带权并查集

并查集记录集合（set）的关系，而带权并查集还要记录元素之间的关系

经典例题：[HDU3038]How Many Answers Are Wrong

题目大意，给出几个区间的和，判断给出的区间中有几个不合法

区间之间的关系，可以转换为向量之间的关系

如图，我们已知sum[x]表示fx到x的和，sum[y]表示fy到y的和

现在我们给出x到y的和z，求sum[fy]即fx到fy的和

显然 sum[fy]=sum[x]+z-sum[y]

而判断合法性，只需要判断sum[y]-sum[x]==z

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int MAXN=200000+5;
 7 int ans;
 8 int f[MAXN],sum[MAXN];
 9 
10 int find(int x)
11 {
12     if(f[x]==x) return x;
13     int root=find(f[x]);
14     sum[x]+=sum[f[x]];
15     return f[x]=root;
16 }
17 
18 int main()
19 {
20     int n,m;
21     while(~scanf("%d%d",&n,&m))
22     {
23         memset(sum,0,sizeof(sum));
24         ans=0;
25         for(int i=0;i<=n;i++) f[i]=i;
26         for(int i=1;i<=m;i++)
27         {
28             int x,y,z;
29             scanf("%d%d%d",&x,&y,&z);
30             x--;
31             int fx=find(x),fy=find(y);
32             if(fx!=fy)
33             {
34                 f[fy]=fx;
35                 sum[fy]=sum[x]-sum[y]+z;
36             }else if(sum[y]-sum[x]!=z) ans++;
37         }
38         printf("%d
",ans);
39     }
40     return 0;
41 }

再介绍几道经典例题：

[HNOI2005]狡猾的商人

[POJ2492]A Bug’s Life

[POJ1182]食物链