HDU - 3038 种类并查集

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

思路：种类并查集的每个节点应该保存它的父节点以及他和父节点之间的关系。假设root表示根结点，sum[i-1]表示i到根结点的和，那么sum[j-1] - sum[i]可以得到区间[j, i]的和。那么给定(x, y, real)可以看作x-1到节点y的和为real

AC代码

#include <cstdio>#include <cmath>#include <cctype>#include <algorithm>#include <cstring>#include <utility>#include <string>#include <iostream>#include <map>#include <set>#include <vector>#include <queue>#include <stack>using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000")#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int>typedef long long LL;const int maxn = 200000 + 5;struct node{int par;int real;}a[maxn];int find(int x, int &root) {if(a[x].par == x) {root = x;return a[x].real;}int r = a[x].real + find(a[x].par, root);//路径压缩a[x].par = root;return a[x].real = r;}bool unionset(int x, int y, int real) {int r1, r2;int rx = find(x, r1), ry = find(y, r2);if(r1 == r2) {if(rx - ry != real) return false;}else { //合并a[r1].par = y;a[r1].real = real - rx;}return true;}int main() {int n, m;while(scanf("%d%d", &n, &m) == 2) {for(int i = 0; i <= n; ++i) {a[i].par = i;a[i].real = 0;}int x, y, r, ans = 0;for(int i = 0; i < m; ++i) {scanf("%d%d%d", &x, &y, &r);if(!unionset(x-1, y, r)) ans++;}printf("%d\n", ans);}return 0;}

如有不当那个之处欢迎指出！