首页 > 代码库 > 并查集-解决区间和纠错问题 hdu-3038
并查集-解决区间和纠错问题 hdu-3038
题目：多次给出信息，告诉你[a,b]区间的和，求多少个错误信息（错误信息不考虑）。
乍一看有点像线段树，但想想就发现这个并不能用线段树方便地解决。后来经提醒是并查集的一种经典题型。
把区间抽象为并查集的子节点和母根结点，子节点存放了到根节点的区间和。这样当引入一个新的区间，如果区间左右界根节点不同就一定不存在矛盾（有点种类并查集的意思，形象来看就是存在冗余区间用于调整），然后可以通过现存集合推导出子节点到根节点的区间和。如果根节点相同则要判断一下是否矛盾（画个图对线段加加减减就能推出公式了，文字不太好描述）。
#include <iostream>#include <cstdio>#define LL long long intusing namespace std;int pre[200005];LL val[200005];int Find(int x){ if(pre[x]==x) return x; int te=Find(pre[x]); val[x]+=val[pre[x]]; return pre[x]=te;}void ini(){ int lx=200000; for(int i=0;i<=lx;i++) pre[i]=i,val[i]=0;}int main(){ cin.sync_with_stdio(false); int n,m; while(cin>>n>>m) { ini(); int u,v,w,ans=0; for(int i=0;i<m;i++) { cin>>u>>v>>w; u--; int t[2]={Find(u),Find(v)}; if(t[0]==t[1]) { if(val[v]-val[u]!=w) ans++; } else { pre[t[1]]=t[0]; val[t[1]]=val[u]-val[v]+w; } } cout<<ans<<endl; } return 0;}
并查集-解决区间和纠错问题 hdu-3038
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。