分类:ACM算法

tarjan算法之割点

tarjan算法之割点
先学tarjan算法,再学割点,优质博客 . 割点也就是把此点去掉后,使无向强连通图至少变成2部分。 1.哪些点是割点? 2.此割点把图割成了几部分? 第一个问题:1.如果根有两个或两个以上的树,那么此点必为割点。 2.如果u不是根节点,它有一个子节点v,并且以v为根节[R...

tarjan算法之缩点

tarjan算法之缩点
1.求至少选几个点作为起点走遍全图(也就是这几个点走的路加起来走遍全图)? 2.求最小加多少边能使图变成强连通图? tarjan缩点求入度为0的点为第一个题的答案,求max(入度为0的点,出度为0的点)为第二个题的答案。 tarjan缩点方法最后给出代码。 疑问: 1.[R...

tarjan算法理解

tarjan算法理解
过程我就不多说了,百度一下,一堆博客。 我参照kuangbin的板子和hdu1269学的基础。 只会敲板子是非常不开心的,所以我自己想了想过程为什么这样写,以下纯属个人理解,如果有错,欢迎指出。 1.我就想为什么在一个连通内只有一个节点dfn[i]==low[i]? 借鉴此博[&...

数据结构之next数组

数据结构之next数组
1.以前学的KMP比较急,其实根本不懂。(重学了一遍,彻底理解) 2.暴力匹配就不多说了,那么有什么办法可以优化呢?那就是向前移动多个位置,但是在移动多个位置的同时,必需满足的是要匹配的字符串必需在前面出现过,而且是从开头,不然你无法判断在移动之后,开头那部分是否相同,这一点应该...

网络流

网络流
网络流之最大流 1.EK算法 跑一遍bfs找到这条路上的最小边minn,sum+=minn,回溯,正向边-minn,反向边+minn。重复这个过程直到没有路可跑。 2.FF算法 跑dfs找到终点,确定最小边minn,回溯,正向边-minn,反向边+minn,sum+=minn[&...

二分图匹配

二分图匹配
kuangbin专题分类 一. 二分匹配 先看一下理论理解一下:http://www.renfei.org/blog/bipartite-matching.html 然后趣学匈牙利算法:一遍就看懂 A,B,C,D,E,G 1.交叉染色判断二分图。 2.二分图最小点[…...

字典树

字典树
1.百度一下“字典树 博客”,第一页的那个能看懂看那个,主要是思想+代码 2.入门题hdu1671 注意释放内存 代码 #include<stdio.h> #include<string> #include<string.h> #incl...

Manacher

Manacher
语言解释:https://segmentfault.com/a/1190000003914228 代码解释:https://www.61mon.com/index.php/archives/181/ 这两个和起来理解的比较清楚。 转载请注明:zxy » Manache...

hash算法

hash算法
1.入门视频https://www.bilibili.com/video/av7230433/ 2.七种题型 (1):给两个字符串s1,s2,求s2是否是s1的子串,并求s2在s1中出现的次数(感觉用kmp比较好)。 (2):给出n个单词串,和一个文章串,求每个单词串是否是文章串...

矩阵

矩阵
1.入门视频:https://v.qq.com/x/page/i03233ew1gm.html 不过这个视频有个错误,就是定义结构体里的数组大小应该和单位矩阵数组大小一样。 2.入门题poj3070 代码:http://paste.ubuntu.com/25713501/ 3[&...