“算法”
算法学习笔记20——网络流费用流
算法学习笔记(20): 网络流费用流 简介 在基础的网络图上,每条边多了一个属性,即费用。这个费用是单位费用,即当这条边有流量 f 的时候,有 f * w 的 费用。 最小费用最大流:在所有的最...
算法学习笔记19——Manacher算法
算法学习笔记(19): Manacher算法 简介: Manacher算法用于解决找到所有回文子串的问题。例如: 给定一个长度为N的字符串s,找到所有的(i, j) 使得 s[i: j]是回文串...
算法学习笔记18——网络流最小割
算法学习笔记(18): 网络流最小割 最小割概念 先忽略网络流,对于一个联通图的割是边的集合,删去这些边可以使原来图上的点集连通性变成两个块。 网络流的割要求两个联通块分别包含S和T(源点和汇点...
算法学习笔记17——tarjan算法
算法学习笔记(17): tarjan算法 tarjan算法在众多问题都有解决方法。 新概念定义 建立在一个有向图的DFS生成树中: graph TD 1((1)) 2((2)) 3((3)) 4...
算法学习笔记16——网络流最大流
算法学习笔记(16):网络流最大流 网络 是一种特殊的带权有向图, 有以下几个特殊概念: 容量:边的权值,流在边上的最大量。 源点:没有入度的点 汇点:没有出度的点 流:每一条边都有对应的流量...
算法学习笔记15——状压DP
算法学习笔记(15):状压DP 状压DP也就是用到了状态压缩思想的动态规划。 状态压缩通常利用01位来对状态进行概括,位运算的效率高,能把看似N的状态直接变成1(前提是N不大) 动态规划都需要状...
算法学习笔记14——AC自动机
算法学习笔记(14):AC自动机 这名字听起来也太高级了,但实际上就是KMP+TIRE树。 所以不妨别管这个名字(Aho–Corasick Automaton) 实际上目的是多字符串匹配查找。 ...
算法学习笔记13——树上启发式合并
算法学习笔记(13):树上启发式合并 启发式算法是根据经验和直观感觉,对算法的优化,也就是指优化容易理解。 树上启发式合并看似高级,实际上是针对树上不带修改的离线子树问题的解决。 离线指的就是树...
算法学习笔记12——CDQ分治
算法学习笔记(12):CDQ分治 CDQ分治是一种思想,将复杂问题转化为简单问题。多维问题转为降维问题。 偏序问题 以一维二维三维偏序作为例子,可以体现CDQ分治的降维思想。 一维偏序 给n个数...
算法学习笔记11——容斥原理的简单应用
算法学习笔记(11): 容斥原理的简单应用 容斥原理 容斥原理本身易于理解,实际上是减去重复计算的部分的思想。 类似于两个有交集的集和并集,就是两个集合相加减去交集。 容斥模型概念 全集:各种...