生之、如舟

并查集

动态规划(8) 博弈论(1) 图论(7) 基本算法(29) 思维(3) 数学(14) 数据结构(5) 数论(18) 最短路(4) 枚举(1) 树状数组(13) 树论(4) 模板(7) 比赛(15) 算法总结(3) 线段树(11) 蓝桥杯(1) 贪心(1)

/ 注册

全部文章 / 并查集（共16篇）

E. Binary Matrix 【并查集】2500

E. Binary Matrix 题意给一个很大的矩阵，问联通块的个数是多少。其中因为矩阵非常大，用的16进制输入的。解法这题非常卡常，光是读入量就已经1.6e7了，所以这里我使用了getchar()来读入。然后对于联通块的个数，就是总的1个数 - 并查集合并的次数考虑一行一行处理并查集...

图论2500 并查集

2020-11-17

0 658

Acwing.240. 食物链【并查集】【带扩展域】来自专栏

240. 食物链题目链接：https://www.acwing.com/problem/content/description/242/ 思路将域扩大成3倍 x 吃 x+N,x+N吃x+2N，x+2N吃x，于是如果出现了x吃y的关系，就可以得出下面图片所示的种族关系。同一个颜色表示同一个物种，...

并查集

2020-04-25

0 971

238. 银河英雄传说【带权并查集】来自专栏

238. 银河英雄传说题目链接：https://www.acwing.com/problem/content/240/ 思路是否在同一个集合很好维护，边带权记录某个节点到祖先(列的第一个节点)的距离就好。然后查询两个节点的间隔就是：abs(w[a]-w[b])-1 代码 #include<...

并查集

2020-04-25

0 820

P1621 集合【暴力】【并查集】来自专栏

P1621 集合题目链接：https://www.luogu.com.cn/problem/P1621 思路发现1e5/2+ 1e5/3 + 1e5/5+1e5/7+....的结果不到1e6，所以可以直接采用暴力，对于每个质因数P把在[L,R]区间的倍数join一下就行代码 #include&...

并查集

2020-04-25

0 837

关押罪犯【并查集】来自专栏

关押罪犯题目链接：https://ac.nowcoder.com/acm/problem/16591 思路见此题的视频讲解：https://www.bilibili.com/video/BV1nz411b75c 代码 #include <iostream> #include <...

并查集

2020-04-25

0 688

2019 ICPC 徐州网络赛 B.so easy 【并查集路径压缩】来自专栏

2019 ICPC 徐州网络赛 B.so easy (并查集) 题目链接：https://nanti.jisuanke.com/t/41384 题目大意给定n个数，从1到n排列，其中有q次操作，操作(1) 删除一个数字 // 操作(2)求这个数字之后第一个没有被删除的数字（包括自己）。思路本题...

并查集

2020-04-14

0 744

POJ1733-Parity game 【带权并查集】

Parity game 题目有一个长度为n的序列给出Q条限制l,r,str str==odd 表示[l,r]区间内的数的和是奇数，否则为偶数请你输出最小的不满足条件的编号-1（即最后一个满足的），如果全部满足，输出总数Q！分析算是一个带权并查集的模板题。dis[i]记录他到根结点的距离，假如a...

并查集

2020-02-19

0 819

ZOJ3261-Connections in Galaxy War 【逆向思维+并查集+离线处理】

Connections in Galaxy War 题目假设有编号从0开始的n个点，每个点都有一个非负权值p[i]。现在有没有重边的m条边和Q个操作。对于操作有两种类型destroy a b 表示摧毁a,b点之间的边query a 表示从a出发能到的点中,权值比a大权值最大,在权值最大前提下编号最...

并查集

2020-02-19

0 700

POJ1456-Supermarket 【贪心+并查集】

Supermarket 题目超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.每天只能卖一个商品.现在你要让超市获得最大的利润. 分析首先涉及到最大利润，那么我们到方案要尽可能到让利润大的商品卖出去，可以考虑利润从大到小排序发现一些什么性质。当我们选...

并查集

2020-02-18

0 848

POJ2492-A Bug's Life 【带权并查集】

A Bug's Life 题意题意很简单，就是给M组虫虫谁喜欢谁的关系，然后判断一下有没有同性恋的虫虫。坑点：每一组数据输出之后还需要输出一个空行分析此题我以前用过二分图来做，这里用带权并查集做。如果存在这么一串关系，x->y->z(x喜欢y，y喜欢z),然后存储x,y,z到根结点...

并查集

2020-02-18

0 988