HDU 3088
[题目大意]
首先输入两个数，M，N，均为自然数。表明有{1，2，3，……，M}连续集合。并有N个陈述语句，表示为a,b,c；意为从集合中的第a个数开始累加，一直到b，他们的总和为c。请你判断这N个陈述句中错误的语句数量。
[核心要点]
这是一个单纯的并查集入门题
[坑]
1.笔者认为题意为输入一组数据，而多次WA后发现正解为多组数据
2.笔者认为原题有一个漏洞，这也是笔者把这道题做难了的原因，读题后，笔者一直认为如下这种大范围，小数据套着小范围，大数据的例题为错，可能出题者没想到吧。
5 2
1 4 9
2 3 16如上，但输出为0，即正确。我们暂时不不纠结这个问题，把此题看作只能如下情况才有解的问题来做。
N M
a b x
b c y
a c z显然，if（x + y == z）则这三例无误，反之有误。
没有这个前提我是真的没有看出来这是一个并查集问题，即使它处在并查集练习题中。
[知识点]
并查集精髓————留空补
首先，并查集通用的三个函数：
| 初始化函数 | init() |
| 查询根元素函数 | find() |
| 合并集合函数 | unite() |
以及，表示状态的par[N],表示权的val[N]
init()函数中，我们通常写作par[i] = i， val[i] = 0;
其中，par[i] = i;可被看作为根元素；
find()函数中，通常找寻一个元素并判断其是否为根元素；此时多会通过函数运算压缩路径，以减少find()函数的无效重复以及代码的清晰。
unite()函数中，对于两个对象，a&&b。首先判断a&&b是否为同一树上。如果是，则可以很容易通过其与根的关系判断出其两者关系是否同题中描述相符。若不是，通常通过函数运算将任一根元素放在另一元素跟下。
初学时曾有这样的想法，如果a的根放在b的根跟下，a下的其他树同a根的关系会不会发生变化呢？
答案是不会的。通过函数变换，例如a子树c，同a的关系用val函数的函数表达式表示，现在再对于树c调用find()函数，返回的为a数的根，即根b。所以现在c同树b作比较时的媒介也变成了树b，即采用b的函数表达式。（对于此题来说，a树下不会有子树）
void init(int n)
{
for(int i = 0 ; i < n ; i++)
{
par[i] = i;
rank[i] = 0;
}
}
int find(int x)
{
if(par[x] == x)
return x;
else
return par[x] = find(par[x]);
}
void unite(int x, int y)
{
x = find(x);
y = find(y);
if(x == y) return;
if(rank[x] < rank[y]) par[x] = y;
else par[y] = x;
if(rank[x] == rank[y]) rank[x]++;
}代码来自《挑战程序设计》
[解法概述]
本题重点涉及庞大子树。即为，既然所有根val值均为0，那么再find()函数中，将val值累加至找到根节点为止，这样就可以维护其与根节点之间的关系。
关于之前提到的函数表达式，=既然需要维护原有一切关系不变。通过下图可知，利用r对新节点a不变的关系列方程：
val[b]+val[r] = val[l]+value;
[AC代码]
#include <iostream>
using namespace std;
const int N = 2e5 + 20;
int par[N], val[N];
int n, m;
int l, r, value;
void init()
{
for (int i = 0; i <= n; ++i)
{
par[i] = i;
val[i] = 0;
}
}
int find(int x)
{
if (par[x] == x) return x;
int t = find(par[x]);
val[x] += val[par[x]];//vital
return par[x] = t;
}
void unite(int a, int b)
{
par[b] = a;
val[b] = val[l] + value - val[r];//vital
}
int main()
{
while (cin >> n >> m)
{
init();
int ans = 0;
for (int i = 1; i <= m; ++i)
{
cin >> l >> r >> value;
l--;
int a = find(l), b = find(r);
if (a == b)
{
if (val[r] - val[l] != value) ++ans;
}
else unite(a,b);
}
cout << ans << endl;
}
return 0;
}PS：图片来自ppt作图2333
推荐博文：