首页 > 代码库 > http://acm.hdu.edu.cn/showproblem.php?pid=3038 并查集权值应用
http://acm.hdu.edu.cn/showproblem.php?pid=3038 并查集权值应用
题意:[1-n]的区间,有m个询问,每个询问表示[e,f]的和是g,问一共有多少组矛盾
sum[i]表示i到根节点的和,求区间和用sum[f]-sum[e-1];
为了简化e--;
因为是并查集 要出来最前面的那个数
1.如果共同祖先相同 直接用sum[f]-sum[e]与给的值g相比较
2.,不是共同祖先包括两种
这种为y>x fa[y]=x; 所以 对应sum[y]=sum[e]+g-sum[f];
还有x>y 让fa[x]=y 所以对应 sum[x]=sum[f]-g-sum[e];
下面 代码
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<vector> #include<math.h> using namespace std; #define ll long long #define INF 0x3f3f3f3f #define maxn 10005 #define N 200005 int fa[N],sum[N]; int Find(int x) { if(x!=fa[x]) { int po=fa[x]; fa[x]=Find(fa[x]); sum[x]+=sum[po]; } return fa[x]; } int main() { int n,m,e,f,g; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0; i<=n; i++) { fa[i]=i; sum[i]=0; } int ans=0; while(m--) { scanf("%d%d%d",&e,&f,&g); e--; int x=Find(e);//查找这个点的父节点 int y=Find(f);if(x==y) { if(sum[f]-sum[e]!=g) ans++; } else if(x<y) { fa[y]=x; sum[y]=g+sum[e]-sum[f]; } else { fa[x]=y; sum[x]=sum[f]-g-sum[e]; } } printf("%d\n",ans); } return 0; }
http://acm.hdu.edu.cn/showproblem.php?pid=3038 并查集权值应用
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。