http://acm.hdu.edu.cn/showproblem.php?pid=3047

带权并差集

 #include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 60000
using namespace std; int f[maxn],d[maxn];
int ans=;
int n,m; int find1(int x)
{
if(x==f[x]) return x;
int f1=f[x];
f[x]=find1(f[x]);
d[x]+=d[f1];
return f[x];
} void union1(int a,int b,int x)
{
int fa=find1(a);
int fb=find1(b);
if(fa!=fb)
{
f[fb]=fa;
d[fb]=d[a]+x-d[b];
return;
}
if(fa==fb)
{
if(d[b]-d[a]!=x) ans++;
}
} void inti()
{
for(int i=; i<=n; i++)
{
f[i]=i;
}
memset(d,,sizeof(d));
ans=;
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
inti();
int a1,b1,x1;
for(int i=; i<=m; i++)
{
scanf("%d%d%d",&a1,&b1,&x1);
union1(a1,b1,x1);
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. js窗口边缘滑入滑出效果-初级代码
  2. 模板短信接口调用java,pythoy版(一) 网易云信
  3. php中的curl】php中curl的详细解说
  4. 隐藏NavigationBar 带来的坑
  5. printf 格式化最常用用法
  6. ruby和Python简单对比
  7. CDOJ 1270 Playfair(模拟)
  8. URL的# (转)
  9. Entity Framework+SQLite+DataBaseFirst
  10. oozie note
  11. was cached in the local repository, resolution will not be reattempted until the update interval of fintech has elapsed or updates are forced
  12. Spring Ioc工作机制 初步
  13. Docker 安装 MySQL
  14. MySQL查询优化注意下面的四个细节
  15. tf.pad(one_hot_encoding, [[0, 0], [1, 0]], mode=&#39;CONSTANT&#39;)
  16. gitlab的md文件内使用锚点
  17. SCP报错:WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!
  18. QT学习笔记6:常见的 QGraphicsItem
  19. Windows下遍历某目录下的文件
  20. 2、Web基本介绍及Html语法介绍

热门文章

  1. mv,Directory not empty不能目录覆盖
  2. xcode忽略警告
  3. Java实现一致性Hash算法深入研究
  4. 跨平台utf8转unicode研究实现(2)
  5. jQuery获取select option
  6. Oracle insert update 时间处理
  7. Android应用开发提高系列(4)——Android动态加载(上)——加载未安装APK中的类
  8. Python进阶之路---1.4python数据类型-数字
  9. 什么是系统平均负载(Load average)
  10. JS高级程序设计学习笔记之RegExp类型