HDU 3038. 带权并查集+前缀和
原题链接
简单
作者:
史一帆
,
2021-05-21 19:47:52
,
所有人可见
,
阅读 202
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int p[N], d[N]; // d[x]存x点到根节点的距离
int n, m;
int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
while (cin >> n >> m)
{
memset(p, 0, sizeof p);
memset(d, 0, sizeof d);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int res = 0;
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a -- ;
int fa = find(a), fb = find(b);
if (fa != fb)
{
p[fb] = fa;
d[fb] = d[a] - d[b] + c;
}
else if (d[b] - d[a] != c)
res ++ ;
}
cout << res << endl;
}
return 0;
}