noip教程--树的相关算法.ppt

树的相关算法,定义,树：要么为空，要么由根结点(root)和n棵子树组成。 森林：若干棵树 二叉树：递归定义 要么为空，要么由根结点左子树和右子树组成 左右子树都是一颗二叉树,如何分辨树,关键词 任意两点有且只有一条路径 N个点M条边的连通图 MN ,图的生成树,最小生成树的两种算法 Prim 邻接矩阵 O(V2) 邻接表 +heap O(E log(V) Kruskal 并查集实现 O(E log(E),图的生成树,最优比率生成树 有带权图G, 对于图中每条边ei, 都有benifiti(收入)和costi(花费), 我们要求的是一棵生成树T, 它使得 (benifiti) / (costi), iT 最大.,二分ans，将每条边减去二分的值*costi,求最大生成树得到边权和sum，若sum0则代表ans还可以变得更大，否则就缩小二分的ans，直到二分到足够的精度为止。,图的生成树,次小生成树 若数据范围较小，可以先求出最小生成树，每次去掉最小生成树上的一条边，再求一遍最小生成树，即为次小生成树。 实现简单，时间复杂度较高。,图的生成树,次小生成树 首先求出原图最小生成树，记录权值之和为MinST。枚举添加每条不在最小生成树上的边(u,v)，加上以后一定会形成一个环。找到环上权值第二大的边(即除了(u,v)以外的权值最大的边)，把它删掉，计算当前生成树的权值之和。取所有枚举修改的生成树权值之和的最小值，就是次小生成树。,图的生成树,对图深度优先搜索，定义DFS(u)为u在搜索树（以下简称为树）中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。根据定义，则有： Low(u)=Min DFS(u) DFS(v) (u,v)为后向边(返祖边) 等价于 DFS(v)DFS(u)且v不为u的父亲节点 Low(v) (u,v)为树枝边(父子边) ,图的dfs树的应用,无向图的割点与割边 一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。 (2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，即u为v在搜索树中的父亲)，使得DFS(u)=Low(v)。 一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)Low(v)。,图的dfs树的应用,有向图的强联通分量 Tarjan O(V+E) 分量形成的拓扑性 缩点+dp,图的dfs树的应用,怕爆栈？ dfs-bfs 非比赛时可使用编译开关 Pascal $m 100000000 C+ #pragma comment(linker,“/STACK:65777216“),树形数据结构,并查集 处理一些不相交集合（Disjoint Sets）的合并及查询问题 路径压缩,团伙 有N个人，M个关系，M个关系中每对X和Y可以是敌人也可以是团伙，是敌人的话，那么敌人的敌人也是团伙。问最多有多少个团伙。,星球大战 一个无向图，有以下两种操作 删去某个点以及其所有关联的边 询问图中有多少联通块,树形数据结构,排序二叉树 多关键字 会退化,已知升序的N个数以及他们的各自需要被访问的次数，要求建立一个最优排序二叉树使得总的访问代价最小。一个结点的访问代价=深度访问次数。,optij 枚举根进行转移 可用四边形不等式优化,树形数据结构,二叉堆 完全二叉树 注意边界 dijkstra+heap,prim+heap,A,B分别为两个单调不减的数列，求所有的Ai*Bj中第K小的项。(N,K=100000),K路归并会做不？,有一篇凹凸不平的矩形地面，面积为m*n，被分为M*N个小正方形，每个正方形有不同的高度，给出矩形中每个正方形的高度，若一场雨后，这块矩形地面最多能积多少体积的水。,树形数据结构,线段树 插入（删除）操作的时间复杂度为O (Log N)。 Lazy 操作,数轴上有很多条线段，数轴上的每个位置都有一个容量，表示这个位置最多能被几条线段覆盖，求能在数轴上最多放置多少条线段。(所有数=100000),树型动态规划,给定一棵树求树上最长路,在树上的一些点放置士兵，每个士兵能监视到的点是自己所在的点和他相邻的点，求最少放置多少士兵能监视到树上所有的点。,在树上的一些边放置士兵，每个士兵能监视到的点是他所在的边连接的两个点，求最少放置多少士兵能监视到树上所有的点。,一棵树，选取一个点当中心的代价是树上每个点到这个点的距离之和，求选取一个点使代价最小。,选课 学校开设了N（N300）门的选修课程，每门课程都有一个学费Wi，每个学生可选课程的数量M是给定的。在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。,状态转移方程 FI,J=MAXFT,K+FI,J-K (0=K=J-1,TSONI);,事实上,我们可以做到O(N2)的优化：考虑一个结点的子结点要么选要么不选，不妨就假定它的子结点一定选，这时候就可以让它带着父结点的最优值加上本身价值继续下一层更新，递归返回时只需比较FT,J与FI,J+1即可。 Procedure treedp(I) For X1 TO SONI,0 T=SONI,X For J0 TO M-1 FT,J