首页 > 代码库 > hdu 3038 (并查集)
hdu 3038 (并查集)
题目大意:
给出m个询问,问【l,r】之间的和 ,求出有多少次询问不和之前的矛盾的。
思路分析:
用并查集记录当前节点到根节点的和。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define maxn 222222 using namespace std; int set[maxn]; int sum[maxn]; int find(int x) { if(x!=set[x]) { int f=set[x]; set[x]=find(set[x]); sum[x]+=sum[f]; } return set[x]; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<=n;i++)set[i]=i,sum[i]=0; int ans=0; while(m--) { int l,r,s; scanf("%d%d%d",&l,&r,&s); l--; int xx=find(l); int yy=find(r); if(xx==yy) { if(sum[l]-sum[r]!=s)ans++; } else { set[xx]=yy; sum[xx]=sum[r]-sum[l]+s; } } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。