win_the_medal
win_the_medal
全部文章
数据结构--并查集
Codeforces(14)
Codeforces (Div.3)(6)
kuangbin带你飞——搜索专题(9)
STL(4)
UVA(2)
动态规划--01背包(1)
动态规划--最长上升子序列(1)
动态规划--最长公共上升子序列(1)
动态规划--最长公共子序列(1)
动态规划--简单DP(4)
图论--SPFA(3)
图论--二分图(1)
图论--差分约束(3)
图论--最小生成树(3)
图论--最短路(10)
字符串--AC自动机(4)
字符串--hash(7)
字符串--KMP(4)
字符串--Manacher(3)
字符串--后缀数组(13)
技巧--二分查找(5)
技巧--前缀和(5)
技巧--大数运算(6)
技巧--尺取法(5)
技巧--拓扑排序(2)
技巧--数据离散化(1)
搜索--BFS(3)
搜索--DFS(20)
数学--gcd和lcm(1)
数学--中国剩余定理(2)
数学--博弈论(2)
数学--快速幂(1)
数学--拓展欧几里得(1)
数学--欧拉函数(1)
数学--矩阵快速幂(1)
数学--素数筛(5)
数学--逆元(1)
数据结构--fhq Treap(2)
数据结构--LCA(1)
数据结构--ST表(2)
数据结构--主席树(1)
数据结构--划分树(1)
数据结构--单调栈与单调队列(4)
数据结构--字典树(5)
数据结构--替罪羊树(1)
数据结构--树状数组(4)
数据结构--树链剖分(8)
数据结构--线段树(15)
牛客(1)
算法--BFPRT(1)
算法--枚举(1)
算法--模拟(7)
算法--贪心(2)
归档
标签
去牛客网
登录
/
注册
win_the_medal的博客
全部文章
/ 数据结构--并查集
(共4篇)
带权并查集(含种类并查集)【经典模板】 例题:①POJ 1182 食物链(经典)②HDU - 1829 A bug's life(简单) ③hihoCoder 1515 : 分数调查
带权并查集: 增加一个 value 值,并且每次合并和查找的时候需要去维护这个 value 例题一 :POJ 1182 食物链(经典) 题目链接:https://vjudge.net/contest/339425#problem/E 带权并查集的解法 定义两个数组fa[ ]和rela...
2019-11-02
0
527
E - 食物链 (拆点并查集)
题目链接:https://vjudge.net/contest/339425#problem/E 思路: 这题原来做的时候用的是种类并查集,但是我忘了。 现在有一个更玄学的做法 因为说白了就是A B C 三个点之间的关系 那么我就把一个点拆成三个点(也就是开三倍的空间) 分别代表这...
2019-11-01
0
728
D - How Many Answers Are Wrong (带权并查集)
题目链接:https://vjudge.net/contest/339425#problem/D 给出一个区间的长度 N,及 M 个子区间和, 形如:x y z, 表示子区间 [x, y] 的和为 z如果一个“子区间和”与前面的“子区间和”冲突,即为错误(而且这个“子区间和”将在接下来的判断...
2019-11-01
1
614
并查集(入门)
首先先看一道很简单的并查集的题目:https://vjudge.net/contest/297398#problem/A 这道题就是让你判断两两城镇之间是否联通 如果不联通就要修建一条道路 就我的理解来说,如果单独使用并查集就是为了合并有相同根结点(或者理解成有相同的性质)的这样的数据 ...
2019-06-22
0
456