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

全栈程序员-站长 • 2022年2月3日下午11:00 • 未分类 • 阅读 41

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; }

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

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115472.html原文链接：https://javaforall.net

全栈程序员-站长

0 0

Laravel 虚拟开发环境 Homestead

Laravel 虚拟开发环境 Homestead

全栈程序员-站长
2021年10月28日
36
Pycharm 中导入模块

Pycharm 中导入模块Pycharm中导入模块@TOC以PyQt5为例1、首先要在安装PyQt5。在windows中以管理员身份打开CRM，然后输入pipinstallpyqt5，安装好pyqt5后，还可以继续安装pyqt5的相关工具，命令pipinstallpyqt5-tools2、在Pycharm中安装pyqt5步骤:File->setting->project:***->p…

全栈程序员-站长
2022年8月27日
6
version control

version control

全栈程序员-站长
2021年7月2日
109
每天一个linux命令（34）：du 命令

每天一个linux命令（34）：du 命令

全栈程序员-站长
2021年10月7日
44
【2022最新Java面试宝典】—— ElasticSearch面试题（31道含答案）

【2022最新Java面试宝典】—— ElasticSearch面试题（31道含答案）目录1.elasticsearch了解多少，说说你们公司es的集群架构，索引数据大小，分片有多少，以及一些调优手段。1.1设计阶段调优1.2写入调优1.3查询调优1.4其他调优2.elasticsearch的倒排索引是什么3.elasticsearch索引数据多了怎么办，如何调优，部署3.1动态索引层面3.2存储层面3.3部署层面4.elasticsearch是如何实现master选举的5.详细描述一下Elasticsearch索引文档的过程6.详细描述一下

全栈程序员-站长
2025年11月4日
5
【Java】JVM垃圾回收机制与类加载机制

【Java】JVM垃圾回收机制与类加载机制不同于C++需要编程人员手动释放内存，Java有虚拟机，因此Java不需要程序员主动去释放内存，而是通过虚拟机自身的垃圾回收器(GarbageCollector-GC)来进行对象的回收。Java语言由于有虚拟机的存在，实现了平台无关性，在任意平台都是通过将代码转换为字节码文件，从而在平台下的虚拟机中运行代码的。JVM内存区域分布虚拟机栈：存放每个方法执行时的栈帧，一个方法调用到…

全栈程序员-站长
2022年5月18日
41

发表回复

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