hdu3047 (带权并查集)

2017年08月16日 8点热度 0人点赞 0条评论

题意:有n个人坐在zjnu体育馆里面,然后给出m个他们之间的距离, A B X, 代表B的座位比A多X. 然后求出这m个关系之间有多少个错误,所谓错误就是当前这个关系与之前的有冲突

#include
#include
#include
#define ll long long
using namespace std;
const int mn=100010;
int n,m,f[mn];
ll d[mn];
int find(int x) {
	if(x==f[x]) return x;
	int t=f[x];
	f[x]=find(f[x]);
	d[x]+=d[t];
	return f[x];
}
int main() {
	while(~scanf("%d%d",&n,&m)) {
		for(int i=1; i<=n; ++i)
			f[i]=i,d[i]=0;
		int ans=0;
		while(m--) {
			int x,y,w;
			scanf("%d%d%d",&x,&y,&w);
			int fx=find(x),fy=find(y);
			if(fx==fy) {
				if(w!=d[y]-d[x])
					++ans;
			} else {
				f[fy]=fx;
				d[fy]=d[x]+w-d[y];
			}
		}
		printf("%dn",ans);
	}
	return 0;
}
未经允许不得转载!hdu3047 (带权并查集)

update

纸上得来终觉浅, 绝知此事须躬行。