#include using namespace std; const int N = 200005; int p[N]; int sum[N]; //权边 //标准的带路径压缩的并查集,查找祖先 int find(int x) { if (x != p[x]) { int i = p[x]; p[x] = find(p[x]); sum[x] += sum[i]; //这里是权累加,就是在路径压缩过程中处理了权的问题 } return p[x]; } // 原题链接 // http://acm.hdu.edu.cn/showproblem.php?pid=3038 int main() { //输入+输出重定向 freopen("../AcWing/N5/HowManyAnswersAreWrong.txt", "r", stdin); int m, n; int ans; while (scanf("%d%d", &m, &n) != EOF) { //初始化并查集 for (int i = 0; i <= m; i++) { p[i] = i;//是有个范围的,每个都是独立的 sum[i] = 0; //初始的权是零 } ans = 0; //处理数据 while (n--) { int l, r, value; cin >> l >> r >> value; l--; int fl = find(l); int fr = find(r); if (fl == fr) { if ((sum[l] - sum[r]) != value) { ans++; } } else { p[fl] = fr;//并查集的合并 sum[fl] = -sum[l] + sum[r] + value;//权值修改 } } cout << ans << endl; } //关闭文件 fclose(stdin); return 0; }