50分求助悬关
查看原帖
50分求助悬关
973971
xfx2011楼主2024/4/6 10:12
#include<bits/stdc++.h>
using namespace std;
long long t;
long long n,m;
const long long maxn = 2e5 + 10;
long long d[maxn];
long long fa[maxn];
long long ans = 0;
int find(int x) {
    if (x == fa[x])
        return x;
    else {
        int fx = find(fa[x]);
        d[x] += d[fa[x]];
        fa[x] = fx;
        return fa[x];
    }
}
void join(long long a,long long b,long long v){
	if(find(a) == find(b)){
		if(d[b] - d[a] != v)
			ans = 1;
	}else{
		fa[find(b)] = find(a);
		d[find(a)] = (d[a] + v - d[b]);
	}
}
void init(){
	
}
signed main(){
 	freopen("the.in","r",stdin);
 	freopen("the.out","w",stdout);
	cin >> t;
	while(t --){
		ans = 0; 
		long long n,m;
		cin >> n >> m;
		for(long long i = 1;i <= n;i ++)
				fa[i] = i,d[i] = 0;
		for(long long i = 1;i <= m;i ++){
			long long a,b,v;
			cin >> a >> b >> v;
			if(ans)
				continue;
			join(a,b,v);
		}
		if(ans)
			cout << "NO\n";
		else
			cout << "YES\n"; 
	}
	return 0;
}
2024/4/6 10:12
加载中...