昨天晚上写了个带权并查集,但是一直没有调出来
他第二个点总是显示的是runtime error,求调!
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int index, len;
}fa[400100];
node find(int n) {
if(n == fa[n].index) {
return fa[n];
}
else
{
node temp = fa[n];
fa[n] = find(fa[n].index);
fa[n].len += temp.len;
return fa[n];
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
cin >> t;
while(t--) {
int n, m;
cin >> n >> m;
for(int i=0; i<=n; ++i) {
fa[i].index = i;
fa[i].len = 0;
}
bool bl = 0;
for(int i=1; i<=m; ++i) {
int x, y, z;
cin >> x >> y >> z;
if(z < 0) {
swap(x, y);
z=-z;
}
node tempa = find(x), tempb = find(y);
int fax = tempa.index, fay = tempb.index, lenx = tempa.len, leny = tempb.len;
// int fax = find(x).index, fay = find(y).index, lenx = find(x).len, leny = find(y).len;
if(fax == fay) {
if(leny == lenx + z) {
continue;
}
else
{
bl = 1;
break;
}
}
else
{
if(lenx + z > leny) {
fa[fay].index = fax;
fa[fay].len = lenx+z-leny;
}
else
{
fa[fax].index = fay;
fa[fax].len = leny-z-lenx;
}
}
if(bl) {
break;
}
}
if(bl) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
}
}
return 0;
}