- it技术
- HDU 3038带权并查集
#include <bits/stdc++.h>
#define ll long long
const int maxn
= 1e6+10;
using namespace std
;
int par
[maxn
];
int height
[maxn
];
int sum
[maxn
];
void init(){
for(int i
= 0; i
<= maxn
; i
++){
par
[i
] = i
;
height
[i
] = 0;
sum
[i
] = 0;
}
}
int Find(int x
){
if(x
!= par
[x
]){
int f
= par
[x
];
par
[x
] = Find(par
[x
]);
sum
[x
] += sum
[f
];
}
return par
[x
];
}
void merge_set(int a
, int b
,int val
){
int fa
= Find(a
);
int fb
= Find(b
);
if (height
[fa
] == height
[fb
]) {
height
[fa
] = height
[fa
] + 1;
par
[fb
] = fa
;
sum
[fb
] = -sum
[b
] + sum
[a
] -val
;
}
else{
if (height
[fa
] < height
[fb
]) par
[fa
] = fb
,sum
[fa
] = -sum
[a
] + sum
[b
] +val
;
else par
[fb
] = fa
,sum
[fb
] = -sum
[b
] + sum
[a
] -val
;
}
}
int main()
{
int n
,m
;
int ans
;
while(~scanf("%d%d",&n
,&m
))
{
ans
= 0;
init();
int a
,b
,val
;
for(int i
= 0;i
< m
;i
++)
{
scanf("%d%d%d",&a
,&b
,&val
);
a
--;
int fa
= Find(a
);
int fb
= Find(b
);
if(fa
!= fb
)
{
merge_set(a
,b
,val
);
}
else{
if(sum
[a
] - sum
[b
] != val
)ans
++;
}
}
cout
<<ans
<<endl
;
}
return 0;
}
