HDU_3038_(并查集合并 线性加)

HDU 3038

• 加权并查集
• 题目描述有问题，有多组数据
• 子序列是连续的，路径压缩是权值相加就行，
• 根节点相同说明已经存在合理字段和，判断到根节点的距离是否满足 已经存在的和
• 不同则合并
  

#include <iostream>
#include <string.h> 
using namespace std;
const int maxn = 2e5+10;
int pre[maxn];
int dist[maxn];

void init() {
	memset(dist,0,sizeof dist);
	for (int i=1; i<maxn; i++) pre[i] = i;
}
int find(int x) {
	int temp = pre[x];
	if (x == pre[x]) return x;
	pre[x] = find(pre[x]);
	dist[x] += dist[temp];
	return pre[x];
}

int main() {
//	freopen("a.txt","r",stdin);
	int n,m;
	
	while (scanf("%d%d",&n,&m) != EOF) {
		init();
		int ans = 0; 
		while (m--) {
			int a,b,len;
			scanf("%d%d%d",&a,&b,&len);
			b++;
			int ra = find(a);
			int rb = find(b);
			if (ra == rb) {
				if (dist[a] - dist[b] != len) 
					ans++;
			}
			else {
				pre[ra] = rb;
				dist[ra] = len + dist[b] - dist[a];
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}