加权并查集 似乎就是在想这题的时候突然理解了之前看E题没看懂的标准加权解法
值得注意的技巧 为了让区间之前连成树 形式设定为为(l, r] 接受l的输入后先自减一下就可以了
#include <iostream> #include <string> #include <cstdio> #include <cmath> #include <cstring> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; int father[200005],sum[200005]; int n,m,ans; int find(int x) { if(father[x] != x) { int tmp = father[x]; father[x] = find(father[x]); sum[x] += sum[tmp]; } return father[x]; } void merge(int x,int y,int s) { int tx = find(x); int ty = find(y); if(tx == ty) { if(sum[x] - sum[y] != s) { ans++; //printf("tx = %d;ty = %d; ", tx, ty); } return; } else { father[tx] = ty; sum[tx] = sum[y] - sum[x] + s; } } int main() { while(~scanf("%d%d", &n,&m)) { for(int i = 0; i <= n; ++i) { father[i] = i; sum[i] = 0; } //printf("father(10) = %d ",father[10]); //printf("find(10) = %d ",find(10)); ans = 0; while(m--) { int x, y, s; scanf("%d%d%d", &x, &y, &s); x--; merge(x, y, s); } printf("%d ",ans); } return 0; }