UVA 10462 kruskal处理次小生成树中重边问题

UVA 10462 prim实在是好难理解如何处理重边,看了6小时的blog没看明白 kruskal原理就是将所有的边排序,然后从小到大处理,正好也将重边给排序了,所有适合处理这个问题 每条边存uesd,del变量,used代表第一次跑出生成树的结果,del代表这条边是否删去 第一次跑完kruskal后,枚举每一条在生成树的边,删除,然后标记(使得下次跑kruskal不在加入到生成树中).在

算法
次小生成树重边问题

POJ 3164 朱刘算法详细解释(最小树形图)

POJ 3164 最小树形图就是有向图的最小生成树 题意:给出n个点,m条边.求有向图的最小生成树题目数据处理 消除图中的自环(自己指向自己的边).改成INF 存点存边朱刘算法原理 首先判断有向图的最小生成树是否存在 dfs (场合不合适) 先判断除根节点外每个点是否有入边,没有入边也不能组成最小生成树.顺便维护除根节点外每个点的的最小入边(最小树形图的边集) 选出的所有点(

算法
最小树形图

HDU_4081_最小生成树+次小生成树性质

HDU 4081 存坐标点然后建图 为了使得总长度(除去一条特殊的道路)可能小.那么求出最短路. 然后枚举图中的每一条边,A已知.B的求法 如果在最小生成树中就将最短路的和-此条边的长度=剩余总长度 如果此边不在最小生成树中.根据生成树的性质,这条边和最小生成树组成环,我们要减去(除去此边)之外的最长边,这样才能使其他的路总和最少(和判断是否存在次小生成树的维护过程一样) 在求最小生

算法

HDU_3642_扫描线求覆盖3次的体积(线段树)

HDU 3642 扫描线模板的基础上增加覆盖次数题意 至少有2个以上不同地点才存在宝藏.即3个以上的空间立体交叉覆盖出的体积,覆盖3次及以上 x y z包括整个库,意思就是给出顶点,观察样例知道是左上和右下的坐标 z<=500.那么扫描法求出平面的面积,在处理题目给出的每一层.求的体积 思路 x用来离散化后作为横轴建线段树,z轴存下来枚举每一个层.x轴坐标离散化后要去重,z轴坐

算法

HDU_1255_扫描线求二次覆盖的面积(线段树)

HDU 1255 在求所有覆盖面积的前提下,求出矩形被覆盖超过2次的区域面积 线段数维护一个len2,表示覆盖>=2次的长度,len1表示覆盖>=1次的长度 add代表区间覆盖的次数 在pushup中,每次add被修改时和update结束时来维护线段树的值 先维护len1,在len1的基础上维护len2 在此之间将浮点坐标存下来(离散化),然后排序并且去重,这样每一个浮点坐

算法
扫描线

HDU_1828_扫描线求周长(线段树维护)

HDU 1828 从下到上扫一遍如何求出横边与竖边的长度? 横边 用一个变量存上一次区间横边覆盖总长度.这一次的区间横边覆盖总长度-上一次区间横边覆盖总长度=此次扫描的横边周长,取绝对值(可能为负数)竖边 线段树维护每个区间覆盖横边的数量(矩形的个数),一个矩形有2个竖边,竖边的长度=下一条横边高度-此条横边高度,所以竖边的周长:2*高度*矩形个数 线段树为了维护一个区间被覆盖

算法

HDU_1542_扫描线求面积(线段树维护)

HDU 1542 一条竖直直线从左到右(反向也行)扫描,那么将扫描出来的直线的y坐标离散化,然后用线段树维护y轴的覆盖区间.x值作为高度 如果一条横着直线从下到上(反向也行)扫描,将扫描出来的x坐标离散化,线段树维护x轴的覆盖区间,y作为高度. 此题从上到下扫,将x坐标离散化,建树 将一个矩形的2条边标记为上边1和下边-1,用线段树维护时不需要延迟标记,因为成对出现,下一次对应边出现就会消

算法
扫描线