这是之前博客园的草稿，写得不好，本来想直接删除了事。然而，斜率优化是一个很重要也很基础的优化问题，是需要学习掌握的。但我现在没有精力写一篇新的文章了。 OI wiki: 斜率优化

我的第一篇洛谷博客就是扫描线。虽然那时候什么也不懂，也非常幼稚，甚至不知扫描线的原理是如何，只是一门心思地去做，就像面对未知的生活。 扫描线处理矩阵面积之和的问题，当然它们会有互相覆盖而不能直接加起来。 扫描线就是从下往上一次扫描“线”，然后用线将图分成多个区域，累加即可。用线段树记录横坐标此时扫描线处的长度。 用 Xi 表示第 \(i\) 条竖直的线（用来划分区间），用 l...

算法介绍 最大流问题是指在一个有向图中，从一个源点到一个汇点，最大化流量，使得所有边的容量都大于等于 0。 dinic 算法是一种高效的求解最大流问题的算法，其时间复杂度为 \(O(EV^2)\)。 dinic 算法的基本思想是，通过增广路算法，找到一条从源点到汇点的增广路，然后通过深度优先搜索（DFS）算法，在增广路上进行流的增广，直到不能再增广为止。 步骤 初始化 fl...

POJ3041 这道题正解对于像我这种蒟蒻来说比较难以想到。 我们发现每次覆盖的只是一条线上的所有点。那么我们可以把它想象成一个二分图，两个集合分别是横轴和纵轴。 想一想，这实际上是不是就是x轴轴和纵轴的最大匹配？ 于是这就变成了一个板子匈牙利算法题目。 1234567891011121314151617181920212223242526272829303132333435363...

最大权闭合子图 闭合子图 定义有向图的一个闭合子图是该有向图的一个点集，其中这个点集中的所有点的出边连向的还是点集中的点。 最大权闭合子图 给有向图的点加一个点权，能得到的点权最大的闭合子图。 网络流模型 将所有正点权的点的点权全部加入答案。接下来我们将原来正点权的点变成负点权。现在图上全是负点，我们需要尽量选最少点权使图符合条件。 设超级源点和超级汇点。 将超级源向所有...

路径覆盖 路径覆盖指一个路径的集合中所有路径点集的并集为原图点集。最小路径覆盖使路径集合大小最小。 路径覆盖分为可否重复选点两种。可重复选点在建模中加大流量即可。 网络流模型 建超级源 \(S\) 和超级汇 \(T\)，将每个点拆点。 将 \(S\) 向所有点 \(i\) 连边，将所有点 \(i'\) 向 \(T\) 连边。 对于原图边集，每一条边 \(u\) 向 ...

定义 这里期望长度表示一段序列连续长度的期望。具体来说，对于一段序列，每个点都有一个概率连续和断开。求所有连续序列和的期望。 当然，对于以上期望长度的定义，我们只需要求出每个点存在的期望的和即可。但是题目永远不会这么简单。 Osu! Osu!是一个音乐游戏，玩家需要对音符在恰当时候进行敲击来通关。一次到位的敲击为o，不到位的为x。一段连续到位的敲击，即combo次数为这段序列的长...

【模板】权值线段树套序列线段树 P3380 【模板】二逼平衡树（树套树） 主要思路如下： 外层为权值线段树，内层为动态开点线段树，也就是每个权值线段树上的节点开一个动态开点线段树。 外层的权值线段树支持查询排名，内层的线段树限制了区间。实际上就是在普通权值线段树上查询的价值变成了在其线段树上区间查询返回的值。 对于这道模板题，我们先写几个函数： 插入 下方的update为外层...

差分 记录相邻节点值的差值。这样一来，前缀和就相当于原值了。 树上差分 树上差分基本上就是差分在树上的实现。因为差分的原理，我们先将所有点的权值改变成差分值，再更改一段区间内的所有值时，只需要更改首尾两端的值，如果要求值的话 dfs 重新加上前缀和就是正常的值了。 P3128 [USACO15DEC] Max Flow P 模板题，发现更改任意两点间的值只需要在两点差分值加...

点分治 点分治是一种树形分治的算法，它选择当前连通块一个重心，将树分成多个连通块进行处理，然后对每个连通块进行分治递归。 树的重心 树上的一个点，满足它的儿子的 \(size\) 的最大值最小。 可以证明，一个树有一个或者两个重心。若有两个重心，它俩一定是直接相连的。 处理问题 求树上给定路径联通的点的对数。我们发现将树分治后，形成了若干个连通块，而且这些连通块必定经过重心。...