GitBook

题目记录

这一题初看还是无法和并查集联系到一起

不过也是通过看了一些文章 找到了与并查集的联系

事实上 如果不考虑并查集的问题 单看这一题 大概思路也可以理出来

告诉的是区间 n,m 那么如果把 1~n和1~m都保存到一个数组 那么 给的输出 便是 sum[m]-sum[n-1]

(sum[MAX_N]保存的是当前数到其根节点的值)

那么当这句话是错误的时候 也就是这一部分的值已经固定了 拿这一部分的值与给的值比较 不相等便是错的

并查集的思想便是在这里对各个关键点进行合并等操作 以此来计算这一部分的值是否为定值

所以这里需要对原来的并查集模板进行一些修改 修改的思路大概可以理清

接收到两个数字 分别作为区间左右端点 如果两数在同一个树上 (两数都与同一个关键点建立过关系 则此区间的值是定值)

示例: 当输入为

10 4 1 10 100 7 10 28 1 3 32 4 6 41

时 运行结果为: 这里写图片描述 需要注意数值为0并不代表真是0 而是给的数据没有对它进行判断

所以要对模板进行如下改动:

find寻找根节点时要把1~自己的和运算并保存 让自己的值加上父节点的值 并在这个过程中通过递归 使得父节点的值加上了它的父节点的值 同时进行了压缩路径 使得其直接与根节点相连 因为根节点之前没有数据成为它的父节点 所以sum[根节点]应该恒为0 从而完成了 寻找根节点的同时进行了从它自身到根节点这个区间值的计算

对于 unite合并操作 则思路为 如果两数根节点相同 则进行判断 否则根据两数根节点的大小进行sum区间的计算 然后进行最两数的关系进行合并

因为sum保存的是其到根节点的值 所以判断出a,b的大小 从而进行赋值

(貌似也有其它思路 不过我觉得问题越复杂 解决的途径有时候越多 所以也不强求自己全部理解别人的其它思路了)

AC代码: 需要注意的是测试数据有多组

#include<stdio.h>
int par[200200];
int sum[200200];
int cnt,t;
int find(int m) {
	if(par[m]==m)
		return m;
	else {
		int t=par[m];
		par[m]=find(par[m]);
		sum[m]+=sum[t];
		return par[m];
	}
}
void unite(int x,int y) {
	int a=find(x);
	int b=find(y);
	if(a==b) {
		if(sum[y]-sum[x]!=t)
			cnt++;
		return ;
	}
	if(a>b) {
		sum[a]=sum[y]-sum[x]-t;
		par[a]=b;
	} else {
		sum[b]=sum[x]+t-sum[y];
		par[b]=a;
	}
}
int main() {
	int N,M;
	while(scanf("%d %d",&N,&M)!=EOF) {
		cnt=0;
		for(int i=0; i<=N; i++) {
			par[i]=i;
			sum[i]=0;
		}
		while(M--) {
			int a,b;
			scanf("%d %d %d",&a,&b,&t);
			unite(a-1,b);
		}
		printf("%d\n",cnt);
	}
	return 0;
}

题目地址:【杭电】[3038]How Many Answers Are Wrong