截图
简介
这是ppt树形结构图，包括了并查集简介，初始化，查找“代表元素”，路径压缩，Kruskal算法，堆的存储，堆的初始化，合并果子等内容，欢迎点击下载。
ppt树形结构图是由红软PPT免费下载网推荐的一款课件PPT类型的PowerPoint.
树形结构 东营市胜利第一中学 高天宇 课件地址 http://yun.baidu.com/s/1bpmLMCf 并查集 并查集简介 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。 举个简单的例子，若A和B互相认识，B和C也互相认识，则A与C互相认识。现在给出若干对这样的关系，询问某两个人是否互相认识。诸如此类的问题可以用并查集解决 并查集简介 并查集首先要记录一组分离的动态集合S={S1，S2，…，Sn}，每个集合还要用一个代表来识别。在一般情况下，每个集合具体选择哪个代表是无所谓的，但前提是，在集合没有发生改变时，询问所得到的代表应该是相同的。 并查集主要有三种操作，初始化，查找与合并。 并查集简介 我们开一个数组father[i]，表示第i个元素所在集合的“代表元素”。 在实际应用中，father[i]并不直接指向“代表元素”，它表示的是一个树形结构。而i所在的树形结构的根才是我们要找的“代表元素” 并查集简介 初始化 开始的时候，每个元素互相独立，各自为一个集合 for (int i = 1; i <= n; i++) father[i] = i; 查找“代表元素” int find(int x) { if (father[x] == x) return x; else return find(father[x]); } 查找“代表元素” 合并 void merge(int x， int y) { int f1 = find(x); int f2 = find(y); fa[f1] = f2; } 合并 路径压缩 不难发现，并查集可以被看作是一些树构成的森林。而朴素的查找操作最坏时间复杂度可以达到𝑂(ℎ)，其中ℎ是树的高度。这显然是难以接受的。 路径压缩 我们可以在执行find函数的时候，顺带着把路径上所有点的father更新成真正的代表元素 int find(int x) { if (father[x] == x) return father[x]; father[x] = find(father[x]); return father[x]; } 路径压缩 路径压缩 在进行路径压缩之后，并查集单次查询的复杂度变为𝑂(𝛼(𝑛))，其中𝛼(𝑛)表示反阿克曼函数。这是一个增长极慢的函数，通常来说，𝛼(𝑛)≤4，我们可以直接把它当成是常数。 Kruskal算法 最小生成树的定义：在一给定的无向图𝐺 = (𝑉， 𝐸) 中，(𝑢， 𝑣) 代表连接顶点𝑢与顶点𝑣的边，而𝑤(𝑢， 𝑣) 代表此边的权重，若存在𝑇为𝐸的子集，使得所有的点联通且为无环图，使得𝑤(𝑇) 最小，则此𝑇为𝐺的最小生成树。 其中𝑤(𝑇)= ∑_((𝑢， 𝑣)∈𝑇)▒〖𝑤(𝑢， 𝑣)〗 Kruskal算法 Kruskal算法 对所有的边按照边权升序排序 对于每一条边(u，v)，查找点u和点v所属的集合。如果两个点已经属于同一集合，则该边不在最小生成树中。否则合并两点所属的集合，该边权计入最小生成树权值和中 Kruskal算法 Kruskal算法 程序自动分析 NOI2015 BZOJ4195 http://www.lydsy.com/JudgeOnline/problem.php?id=4195 程序自动分析 我们可以用并查集维护所有数之间的相等关系。先处理所有的等式，将等式两边的两个数所在的集合合并在一起 然后我们检查所有的不等式。如果某个不等式两边的数字在一个集合中（被要求相等），则输出NO。不存在这样的情况则输出YES Connect 给定一个点数为𝑁、边数为𝑀的无向图，请编写一个程序支持以下两种操作： 1、𝐷 𝑥 𝑦，在原图中删除连接顶点𝑥和顶点𝑦的边。 2、𝑄 𝑥 𝑦，询问𝑥顶点和𝑦顶点是否联通。 𝑁， 𝑀 ≤500，000 Connect 带有路径压缩的并查集并不支持分离操作 那我们如何实现题目中的“删除”？ 离线处理 将所有的操作倒序处理，就变成了连接两个点，询问两个点是否在同一集合中。如此就可以使用并查集了 Cube Stack 有𝑁个立方体，初始时每个立方体都在独立的一个栈中。支持两个操作： 1、𝑀ove 𝑎 𝑏，把包含立方体𝑎的栈整体移动到包含立方体𝑏的栈顶（两栈合并） 2、𝐶𝑜𝑢𝑛𝑡 𝑎，询问立方体𝑎下方有多少个立方体。 𝑁≤30，000 Cube Stack 并查集解决毫无疑问，重点是如何完成路径压缩部分的编程。 定义𝑓[𝑘]为立方体𝑘所属栈的栈底元素，𝑐𝑛𝑡[𝑘]为立方体𝑘到所属栈底的元素个数，𝑡𝑜𝑝[𝑘]为立方体𝑘所属栈的栈顶元素。 对于𝑓𝑖𝑛𝑑函数： Cube Stack int find(int x) { if (f[x] == x) return x; int fa = f[x]; f[x] = find(fa); cnt[x] += cnt[fa] - 1; return f[x]; } Cube Stack 对于𝑚𝑒𝑟𝑔𝑒函数： void merge(int x， int y) { int f1 = find(x)， f2 = find(y); f[f1] = f2; cnt[f1] = cnt[top[f2]] + 1; top[f2] = top[f1]; } 食物链 动物王国中有三类动物A，B，C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 现有N个动物，以1－N编号。每个动物都是A，B，C中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述： 第一种说法是"1 X Y"，表示X和Y是同类。 第二种说法是"2 X Y"，表示X吃Y。 食物链 此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 1） 当前的话与前面的某些真的话冲突，就是假话； 2） 当前的话中X或Y比N大，就是假话； 3） 当前的话表示X吃X，就是假话。 你的任务是根据给定的N（1 <= N <= 50，000）和K句话（0 <= K <= 100，000），输出假话的总数。 食物链 首先，如果出现1 x y或者2 x y，x和y之间将会建立一种联系。而没有联系的两个动物之间没有任何关系或者影响。所以我们把有联系的动物放入并查集。 我们开一个数组type[i]，记录i号动物的种类情况。种类有三种，分别记为0，1，2，1吃0，2吃1，0吃2。对于每一个并查集，我们取根节点的类型为0 食物链 合并的时候，我们需要相对应的修改各自的type值。 Find them， catch them 有𝑁个罪犯，他们每个人都属于两个帮派中的一个。给出𝑀条操作： 1、𝐷 𝑎 𝑏，表示a和b属于不同帮派。 2、𝐴 𝑎 𝑏，询问a和b是否属于同一帮派，或无法判断。 𝑁≤100，000， 𝑀≤100，000 Find them， catch them 用并查集维护是否相关联。 令𝑑[𝑖]表示𝑖元素到集合根节点的距离。 对于操作𝐷 𝑎 𝑏，合并a，b所在集合，同时维护一下d 如何维护d？ 查询？ 如果𝑎和𝑏在不同集合，则关系不能确定。 如果𝑎和𝑏到根节点的距离奇偶相同，则属于同一帮派。否则属于不同帮派。 堆 堆 堆是什么？ 一堆吃的？ 一堆人？ No，No，No。。。 是一堆数字。。 堆 堆是一棵完全二叉树 不仅仅是完全二叉树 堆 大根堆 每个节点的权值都比儿子的权值大 小根堆 每个节点的权值都比儿子的权值小 因为堆的性质，大根堆的根节点一定权值最大，小根堆的根节点一定权值最小 堆的存储 只需要一个数组就可以搞定 令heap[1]存储根节点。 对于每个点i来说，heap[i * 2]存储左儿子，heap[i * 2 + 1]存储右儿子 堆的存储 筛选 假设有一个堆heap[1..n]，我现在要删除第一个元素（最大的元素），如何维护堆的性质不变？ 将根节点删除，把最后一个点移动到根节点上来。如果当前点比某一个儿子小，就与儿子交换（如果比两个儿子都小，与最大的儿子交换），以此类推，直到没有儿子或者比儿子大 筛选 筛选 void heap_adjust(int x) { while (x*2<=tot) { int j=x*2; if (x*2+1<=tot&&heap[x*2+1]>heap[x*2]) j++; if (heap[j]>heap[x]) swap(heap[x]，heap[j])，x=j; else break; } } 筛选 为何是正确的？ 必要条件：子树是一个合法的堆 堆的初始化 现在我们有一个数组a[1..n]，如何把它初始化成一个堆？ 从编号大的点，到编号小的点，依次进行“筛选”操作 堆的初始化 for (int i = tot / 2; i >= 1; i--) heap_adjust(i); 为什么是对的？ 每次对一个点做调整的时候，它的子树一定都已经是合法的了 对1节点进行调整后，整个堆就是合法的了 加入新的点 如何在堆中加入新的节点？ 如果现在堆中共有tot个节点，我们把新的节点放在位置tot+1上。 运用和“筛选”类似的方法，我们不停地比较当前点和父亲，如果当前点比父亲大，则交换，直到交换到根或者不再比父亲大为止。 加入新的点 加入新的点 正确性？ 除了新的点到根路径上的这些点，其余点都满足比父亲小 经过调整后，路径上的点也合法了 堆排序 将整个序列调整为堆 提取出根节点，输出，并删除。将最后一个点放到根节点的位置，进行“调整”。“调整”后，仍然满足堆的性质。 重复第二步，直到所有的元素都被删除。 合并果子 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 合并果子 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。 合并果子 经典模型：哈夫曼树 给定n个权值作叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。 合并果子 合并果子 显然，我们要让权值大的路径短（离根近），权值小的路径长（离根远） 运用堆。将所有的权值建成一棵小根堆。每次提取出最小的两个点（相当于两堆水果），合并，加入答案，并重新放回堆中 正确性？保证了权值小的路径长，权值大的路径短
展开
