题目描述
http://acm.hdu.edu.cn/showproblem.php?pid=3038
带权并查集区间操作经典题
Solution
首先我们思考什么情况下会出现矛盾
显然是首尾相连（注意不能使相交的区间）的小区间将大区间截得只剩一个区间时，那个区间的值是已知的，这种时候可能出现矛盾
我们考虑用并查集维护区间，因为本题区间是离散的，所以我们考虑将右节点加一，这样并查集就能把区间连起来
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
| #include <iostream>
#include <cstdio>
#define maxn 200010
using namespace std;
int n, m;
int fa[maxn], d[maxn];
void init_fa() { for (int i = 1; i <= n + 1; ++i) fa[i] = i, d[i] = 0; }
int find(int x) {
if (fa[x] == x) return x;
int fx = fa[x]; fa[x] = find(fa[x]);
d[x] += d[fx];
return fa[x];
}
inline void merge(int x, int y, int z) { fa[x] = y; d[x] = z; }
int ans;
int main() {
while (cin >> n >> m) {
init_fa(); ans = 0;
for (int i = 1; i <= m; ++i) {
int l, r, w, fl, fr; scanf("%d%d%d", &l, &r, &w); ++r;
fl = find(l); fr = find(r);
if (fl == fr) ans += d[l] - d[r] != w;
else merge(fl, fr, d[r] - d[l] + w);
}
cout << ans << endl;
}
return 0;
}
|