Dydong
Splay Splay
Splay 概述 平衡树,尽量把时间复杂度压到nlogn,支持的方面有区间修改区间查询,区间翻转,区间删除,整段最大子序列,查询第K大的数,查询数是第几大。也可以运用在树套数中。 核心函数 核心思想通过判断节点的关系如果是直线则先右旋再
2022-05-15
朱刘算法 朱刘算法
朱刘算法 概述朱刘算法也称为有向图的最小生成树,我们把其中的图称为最小树形图。它的特点是没有环,同时除了起始点外每一个点的入度都为1。它的算法流程是这样的:1.对于每一个点找一条入边为权值最小的边。2.判断选出的边是否存在环,如果无环则直接
2022-05-06
费用流2 费用流2
费用流2 网格图 费用流的网格图一般都是找路线,可以解决很多dp解决不了的问题,同时也可以解决数字三角形的变态魔改问题,其中最重要的是拆点限流增边。 acwing2191: ​ 梯形的第一行有 m 个数字。(相当于数字三角形第n层开始)
2022-05-04
费用流1 费用流1
费用流1 概述费用流,也叫作最小费用最大流,是指在普通的网络流图中,每条边的流量都有一个单价,求出一组可行解,使得在满足它是最大流的情况下,总的费用最小。做法一般都是简单地SPFA(也就是和EK算法类似),时间复杂度比较高,所以一般规模都挺
2022-05-01
最短路 最短路
最短路 Bellman_Fordbool bellman(int p) { for(int i=1;i<=n;i++) dist[i]=(i==p?0:inf); for(int i=1;i<=n;i++) //实
2022-04-30
最小割1 最小割1
最小割1 概述 在最大流的定理我们证明了在最大流没有增广路,同时如果割的流量等于它的容量那么这个流是最大流。因此可以得出最大流是最小割。直接用dinic模板去求即可,然后如果从s点可以遍历到的点即为S集合,否则为T集合。 例题给出一个带
2022-04-30
最小割3(二分图) 最小割3(二分图)
最小割3(二分图) 最小权覆盖集概述选取任意的点,使得点集可以包含所有的边(每一条边的顶点至少有一个被选择)。 证明 首先进行图的二分然后从S到左边图连一个容量为点权的边,右边图连一个向T容量也为点权的边,中间的点都用inf相连,可以发现构
2022-04-30
最小割2 最小割2
最小割2 最大权闭合图定义最大权闭合图是指在一个有向图里,每一个点有一个对应的权值,可以有负数,然后求一个子图,其中这个子图没有向外的边,但可以存在外面连向子图的边。子图中每一个点不一点相连。求最大权值。 证明我们首先假设任意的一个子图为v
2022-04-30
数论1 数论1
数论1 欧几里德算法欧几里德算法是一个最广为人知的算法,求两个数的最大公因数,可以调用algorithm里的函数,也可以手写: #include<iostream> #include<algorithm> using name
2022-04-30
数论2 数论2
数论2 排列组合 加法原理:p1+p2+p3+..+pn; 乘法原理:p1xp2xp3x..xpn; 容斥原理:|AUBUC|=|A|+|B|+|C|-|AnB|-|BnC|-|AnC|+|AnBnC|; 杨辉三角 根据杨辉三
2022-04-30
Tarjan Tarjan
Tarjan 概述tarjan问题主要处理有向图的强连通分量和无向图的割点桥甚至是LCA问题,本文主要介绍前两者,后者请看之前的博客。 强连通分量 这类的问题主要是判环问题,是否在子图中存在两两互通的点。 思路是随意选择一个点作为根节点
2022-04-30
LCA(公共父节点) LCA(公共父节点)
LCA(公共父节点) 前述:​ 求LCA的方式有许多,如一般解法,Tarjan,ST表等。这里介绍一下前两种。 问题概述 一般解法 tarjan 问题概述:​ 已知有一棵树求所问的每两个节点的公共父节点(深度最深),如图所示:求4,
2022-04-30
2 / 4