Howmany answers are wrong

带权并查集

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 200005;
int f[maxn], sum[maxn];
int find(int x){                     //带权值的路径压缩
  if (x == f[x]) return f[x];        //返回节点
  int k = find(f[x]);                //递归最后返回根节点
  sum[x] += sum[f[x]];               //进行和的更新
  return f[x] = k;                   //返回根节点
}
void init(int n){                    //初始化
  for (int i = 0; i <= n; ++i){
    f[i] = i;                        //集
    sum[i] = 0;                      //权值
  }
}
void solve(){
  int n, m;
  while(~scanf("%d%d", &n, &m)){
    init(n);
    int l, r, w, ans = 0;
    while (m--){
      scanf("%d%d%d", &l, &r, &w);
      l--;                          //根据区间合并原理，左端点需-1.
      int sl = find(l);
      int sr = find(r);
      if (sl == sr && sum[r] - sum[l] != w){       //不合理输入+1
        ans++;
      }
                                    //进行合并时，默认最左端点为父亲。
      else if (sl > sr){            //比较节点的集
        f[sl] = sr;                 //优化：短树并长树
        sum[sl] = sum[r] - sum[l] - w;             //右端减去左端的数值减去权值
      }
      else if (sl < sr){
        f[sr] = sl;
        sum[sr] = sum[l] - sum[r] + w;
      }
    }
    printf("%d\n", ans);
  }
}
int main(){
  solve();
  return 0;
}

笔记：路径压缩可以将原来的操作低效的“长”树根优化成“短”的树根，每个节点直连根节点，带权值的x和节点合并后在符合题目的前提下权值也要更新