问题描述
问题分析
需要注意数值为0并不代表真是0
而是给的数据没有对它进行判断
所以要对模板进行如下改动:
find寻找根节点时要把1~自己的和运算并保存
让自己的值加上父节点的值
并在这个过程中通过递归
使得父节点的值加上了它的父节点的值
同时进行了压缩路径
使得其直接与根节点相连
因为根节点之前没有数据成为它的父节点
所以sum[根节点]应该恒为0
从而完成了 寻找根节点的同时进行了从它自身到根节点这个区间值的计算
对于 unite合并操作
则思路为
如果两数根节点相同 则进行判断
否则根据两数根节点的大小进行sum区间的计算
然后进行最两数的关系进行合并
因为sum保存的是其到根节点的值
所以判断出a,b的大小 从而进行赋值
(貌似也有其它思路 不过我觉得问题越复杂 解决的途径有时候越多 所以也不强求自己全部理解别人的其它思路了)
AC代码:
需要注意的是测试数据有多组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #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