Tarjan求割点原理 + UVA 315

割点无向图中.删去节点x,及其所有与x关联的边后.分成2个及以上的不相连的子图.则称x是图的割点 搜索树:dfs遍历无向图的访问的顺序.每个点只遍历了一次,生成的树割点判定法则 x不是搜索树的根节点,且存在y是x的子节点. 满足low[y]>=dfn[x] 说明从y或y子树出发的点能访问到的最早的点只能达到x点(low[y]==dfn[x]),不能到达dfs访问更早的点.这

算法
割点板子

HDU 4408 最小生成树计数详细解释

一些blog看我的好迷,假解释看哭我了,这是我自己的理解,一道题看1天.菜哭HDU 4408 无向图的最小生成树计数原理 就是在kruskal处理边的时候不断地找到联通块(由多个同长度的边组成的联通块),取任意一条都满足最小生成树,取不同的相同长度的边就是不同的最小生成树 在遇到排好序的相同长度的边时,(看作一个阶段).已经使得边满足最小的概念,求出生成树的个数. 变量含义 vis[]代表每

算法

HDU 4305 无向图生成树计数+思维建边

HDU 4305 能够构成边的前提: 距离<=R 两点之间的直线上,没有其他点阻碍. 存点.然后2层for遍历每个点.建边判断2点直线上是否存在其他点 根据2个点的x坐标的的大小,将xa,ya存下左边点,xb,yb存下右边的点. 遍历除取这2个点之外的点.首先根据每个点的x坐标是否处于xa,xb中间来判断是否可能阻断2点的连线(只有在2点中间才可能在2点所连接的直线上) 左边点和遍

算法

HDU 4009 无定根最小树形图(依据题意建根)

HDU 4009 给出3维的点,由每个点的信息建立一个有向图,然后求出最小树形图 建图方法:先把每个点的信息存着.根据每个点指向的另一个点的高度来建边, p[i].z >= p[to].z,就不需要水泵p[i].z < p[to].z,加上一个水泵 题目告诉可以挖井是什么意思?题目也没有给出有向图的原点,我们又需要建一个虚根作为原点.那么可以将所有井的底部都抽象成虚根,正

算法

HDU 2121 无定根最小树形图

HDU 2121 题目给出有向图,求出最小生成树同时求出根节点. 首先要会朱刘算法.将不定根构造成求定根,在求定根的朱刘算法板子上修改一下.方法 构造一个定根(0,此题点从1-n),该定根连接图中每一个点.并且权值是>原图所有边的权值和的任何值,我们取sum+1,求出来的 生成树的和-构造的边的和(sum+1)就是不定根的最小树形图的和, 取>原图权值和的原

算法