HDU 2121 无定根最小树形图
HDU 2121 题目给出有向图,求出最小生成树同时求出根节点. 首先要会朱刘算法.将不定根构造成求定根,在求定根的朱刘算法板子上修改一下. 方法 构造一个定根(0,此题点从1-n),该定根连接图中每一个点.并且权值是>原图所有边的权值和的任何值,我们取sum+1,求出来的 生成树的和-构造的边的和(sum+1)就是不定根的最小树形图的和, 取>原图权值和的原因是让构造
emerald's blog
UVA 11183 最小树形图板子
UVA 11183 有向图的最小生成树. 朱刘算法板子123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include <iostream>
UVA 10462 kruskal处理次小生成树中重边问题
UVA 10462 prim实在是好难理解如何处理重边,看了6小时的blog没看明白 kruskal原理就是将所有的边排序,然后从小到大处理,正好也将重边给排序了,所有适合处理这个问题 每条边存uesd,del变量,used代表第一次跑出生成树的结果,del代表这条边是否删去 第一次跑完kruskal后,枚举每一条在生成树的边,删除,然后标记(使得下次跑kruskal不在加入到生成树中).在跑一
UVA 10600 prim次小生成树
UVA 10600 次小生成树prim板子 代码第44行.发现更新最小生成树中的maxdist[][](2点之间的最大边),不能更新point,也就是刚加入生成树中的点,这样就会更新自环，变成了dist[point],而自环应该是012345678910111213141516171819202122232425262728293031323334353637383940414243444546
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 在此之间将浮点坐标存下来(离散化),然后排序并且去重,这样每一个浮点坐标都