hdu3047带权并查集

69 阅读 0 评论 46 点赞

我是靠谱客的博主矮小微笑，最近开发中收集的这篇文章主要介绍hdu3047带权并查集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

hdu3047

题解：带权并查集裸题

#include <bits/stdc++.h>
using namespace std;
int const N = 50000 + 10;
int n,m,a,b,x,f[N],val[N];
int find(int x){
	if(x != f[x]){
		int t = f[x];
		f[x] = find(f[x]);
		val[x] += val[t];
	}
	return f[x];
}
int main(){
	ios::sync_with_stdio(false);
	while(cin>>n>>m){
		int ans = 0;
		for(int i=0;i<=n;i++)	f[i] = i,val[i] = 0;
		for(int i=1;i<=m;i++){
			cin>>a>>b>>x;  //b编号比a大x
			int fa = find(a),	fb = find(b);
			if(fa != fb){
				f[fb] = fa;
				val[fb] = val[a] + x - val[b];
			}else if(val[b] - val[a] != x)	ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}