hdu3038 How Many Answers Are Wrong 扩展并查集
hdu 3038(扩展并查集)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3038
题意:给出区间[1,n],下面有m组数据,l r v区间[l,r]之和为v,每输入一组数据,判断此组条件是否与前面冲突 ,最后输出与前面冲突的数据的个数.
比如 [1 5]区间和为100 然后后面给出区间[1,2]的和为 200 那肯定就是有问题的了。
极力推荐这位大牛的博客:http://blog.****.net/niushuai666/article/details/6981689
这题让我学到了很多,特别是关于向量偏移,可以直接找到根节点与子节点的关系
这题我们利用一个sum[]数组保存从某点到其祖先节点距离。
1.从上图我们可以看出,当roota!=rootb时 如果将roota并入rootb,那么是不是 roota->rootb = b->rootb - b->roota
然后我们可以知道 b->roota = a->roota - a->b
所以最后可以推出 roota ->rootb = b->rootb + a->b - a->roota
而roota的根节点是rootb,所以 roota->rootb = sum[roota]
然后依次推出得到 sum[roota] = -sum[a]+sum[b]+v (这里的a要说明一下由于是区间 [a,b] ,[a,b] = [root,b]-[root,a-1],所以a要减一)
2.如果roota==rootb 是不是 a和b的根节点已经相同了?所以我们只要验证 a->b是否与题中的长度一致了。
所以 a->b = a->root - b->root
然后得到表达式 v = sum[a]-sum[b] (一定要记住这里的sum都是相对于根节点的,sum的更新在路径压缩的时候更新了)
这样说是不是懂了向量偏移的思想呢??
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,ans=0;
int f[200005];
int sum[200005];
int find(int x){
if(f[x]==x)
return x;
int t = f[x];
f[x] = find(f[x]);
sum[x]+=sum[t];
return f[x];
}
void Union(int x,int y,int v){
int a = find(x);
int b = find(y);
if(a==b){
if(sum[x]-sum[y]!=v){//如果祖先是同一个了,就可以验算
ans++;
return;
}
}else{
f[a] = b;
sum[a] = -sum[x]+sum[y]+v;
}
return;
}
int main(){
while(~scanf("%d%d",&n,&m)){//等价于scanf("%d%d",&n,&m)!=EOF
for(int i=0;i<=n+5;i++){//每一次都是要初始化的
f[i] = i;
sum[i] = 0;
}
ans=0;
while(m--){
int a,b,v;
scanf("%d%d%d",&a,&b,&v);
Union(a-1,b,v);//别忘了a-1
}
printf("%d\n",ans);
}
return 0;
}