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账号...