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

《noip教程-树的相关算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树的相关算法定义树：要么为空，要么由根结点(root)和n棵子树组成。森林：若干棵树二叉树：递归定义要么为空，要么由根结点左子树和右子树组成左右子树都是一颗二叉树如何分辨树关键词任意两点有且只有一条路径N个点M条边的连通图M

2、树T,它使得∑(benifit[i])/∑(cost[i]),i∈T最大.二分ans，将每条边减去二分的值*cost[i],求最大生成树得到边权和sum，若sum>0则代表ans还可以变得更大，否则就缩小二分的ans，直到二分到足够的精度为止。图的生成树次小生成树若数据范围较小，可以先求出最小生成树，每次去掉最小生成树上的一条边，再求一遍最小生成树，即为次小生成树。实现简单，时间复杂度较高。图的生成树次小生成树首先求出原图最小生成树，记录权值之和为MinST。枚举添加每条不在最小生成树上的边(u,v

3、)，加上以后一定会形成一个环。找到环上权值第二大的边(即除了(u,v)以外的权值最大的边)，把它删掉，计算当前生成树的权值之和。取所有枚举修改的生成树权值之和的最小值，就是次小生成树。图的生成树对图深度优先搜索，定义DFS(u)为u在搜索树（以下简称为树）中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。根据定义，则有：Low(u)=Min{DFS(u)DFS(v)(u,v)为后向边(返祖边)等价于DFS(v)

4、亲节点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)bf

5、s非比赛时可使用编译开关Pascal{$m100000000}C++#pragmacomment(linker,"/STACK:65777216")树形数据结构并查集处理一些不相交集合（DisjointSets）的合并及查询问题路径压缩团伙有N个人，M个关系，M个关系中每对X和Y可以是敌人也可以是团伙，是敌人的话，那么敌人的敌人也是团伙。问最多有多少个团伙。星球大战一个无向图，有以下两种操作删去某个点以及其所有关联的边询问图中有多少联通块树形数据结构排序二叉树多关键字会退化已知升序的N个数以及他们的

6、各自需要被访问的次数，要求建立一个最优排序二叉树使得总的访问代价最小。一个结点的访问代价=深度×访问次数。opt[i][j]枚举根进行转移可用四边形不等式优化树形数据结构二叉堆完全二叉树注意边界dijkstra+heap,prim+heap…A,B分别为两个单调不减的数列，求所有的Ai*Bj中第K小的项。(N,K<=100000)K路归并会做不？有一篇凹凸不平的矩形地面，面积为m*n，被分为M*N个小正方形，每个正方形有不同的高度，给出矩形中每个正方形的高度，若一场雨后，这块矩形地面最多能积多少体积

7、的水。树形数据结构线段树插入（删除）操作的时间复杂度为O(LogN)。Lazy操作数轴上有很多条线段，数轴上的每个位置都有一个容量，表示这个位置最多能被几条线段覆盖，求能在数轴上最多放置多少条线段。(所有数<=100000)树型动态规划给定一棵树求树上最长路在树上的一些点放置士兵，每个士兵能监视到的点是自己所在的点和他相邻的点，求最少放置多少士兵能监视到树上所有的点。在树上的一些边放置士兵，每个士兵能监视到的点是他所在的边连接的两个点，求最少放置多少士兵能监视到树上所有的点。一棵树，选取一个点当中心

8、的代价是树上每个点到这个点的距离之和，求选取一个点使代价最小。选课学校开设了N（N<300）门的选修课程，每门课程都有一个学费Wi，每个学生可选课程的数量M是给定的。在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。状态转移方程F[I,J]=MAX{F[T,K]+F[I,J-K]}(0<=K<=