HDU 3047 Zjnu Stadium 带权并查集[通俗易懂]

HDU 3047 Zjnu Stadium 带权并查集

大家好,又见面了,我是全栈君。

题目来源:#include <cstdio> #include <cstring> using namespace std; const int maxn = 50010; int f[maxn], flag[maxn], sum[maxn]; int cnt; void init(int n) { for(int i = 1; i <= n; i++) f[i] = i; //memset(rank, 0, sizeof(rank)); memset(sum, 0, sizeof(sum)); } int find(int x) { if(x != f[x]) { int rt = find(f[x]); sum[x] += sum[f[x]]; f[x] = rt; return rt; } return f[x]; } void merge(int i, int j) { int x = find(i); int y = find(j); if(x != y) { f[y] = x; } } int main() { int n, m; while(scanf("%d %d", &n, &m) != EOF) { init(n); int ans = 0; while(m--) { int w, u, v; scanf("%d %d %d", &u, &v, &w); int x = find(u); int y = find(v); if(x != y) { f[y] = x; sum[y] = sum[u] - sum[v] + w; } else { int sum1 = sum[u]; int sum2 = sum[v]; if(sum2-sum1 != w) ans++; } } printf("%d\n", ans); } return 0; }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115472.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号