HDU 3038 How Many Answers Are Wrong 带权并查集
分析：这一题和HDU3047一样，都是带权并查集，求后输入和先输入的冲突个数
然后其实就是用并查集维护一棵树，小的作为大的祖先，然后这棵树每个节点到根的路径权值是相对根节点的距离
这样就可以维护距离限制，判断冲突
#include <cstdio> #include <cstring> #include <queue> #include <set> #include <map> #include <stack> #include <cstdlib> #include <algorithm> #include <vector> #include <cmath> using namespace std; const int N=2e5+5; int n,m,fa[N],sum[N]; int find(int x){ if(x==fa[x])return fa[x]; int t=fa[x]; fa[x]=find(fa[x]); sum[x]+=sum[t]; return fa[x]; } int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=0;i<=n;++i)fa[i]=i,sum[i]=0; int ans=0; while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); --u; int x=find(u),y=find(v); if(x==y){ if(sum[v]-sum[u]!=w)++ans; } else if(x>y){ sum[x]=sum[v]-sum[u]-w; fa[x]=y; } } printf("%d ",ans); } return 0; }