Moench 的算法宝库

无向图的双连通分量(DCC) 可分为 边双连通分量(e-DCC) 与 点双连通分量(v-DCC) 注意： 点双连通分量不一定是边双连通分量，边双连通分量也不一定是点双连通分量 割点与桥没有什么本质的关系 两个割点之间的边不一定是桥 一个桥的两个端点不一定是割点 边双连通分量(e-DCC)介绍 桥：一条无向边，若删除此边，整个图变得不连通，则称这条边为“桥”。 边双连通分量：极大的不包含“桥”的连通块，则称为“边的双连通分量” 性质： 无论删除哪一条边，整个图一定还是连通的 任意两点之间一定包含两条不相交的路径(边不相交)。 Tarjan算法求边的双连通分量 时间戳(timestamp)，dfn[N], low[N], 和有向图的强连通分量作用相同 如何找到桥？ 若子节点可以走到父节点或祖先节点，则从父节点到子节点的边不是桥，等价于，若边 x-y 为桥，则 dfn[x] < low[y] 如何找到边双连通分量？ 方法一：将所有桥删去 方法二：类似于有向图的强连通分量的Tarjan算法，用栈(stk数组)维护，刚开始搜索加到栈里，若dfs[i] == low[i]的话( ...

有向图的强连通分量(SCC) 强连通分量 : SCC, 有向无环图 : DAG 介绍： 默认前提为有向图。 连通分量：对于分量中的任意两点 u, v, 必然存在可以从 u 走到 v, 且从 v 走到 u 。 强连通分量 (SCC)：极大连通分量，(无法加入任何点的连通分量) 作用： 将任意一个有向图，通过 缩点 ，转化为有向无环图(拓扑图，DAG) 缩点：将所有连通分量缩成一个点 好处是求最短路或最长路时，可以递推来做，时间复杂度为 线性: O(n + m) Tarjan算法理论基础： 按照 DFS 的顺序来求 把边分为四类 树枝边 (x, y)：x 是 y 的父节点 前向边 (x, y)：x 是 y 的祖先节点 (x -> y) 后向边 (x, y): 指向祖先节点的边 (y -> x) 横叉边 (x, y): 指向之前搜过的边 如何判断一个点是否在强连通分量中？ 情况1：存在后向边直接指向祖先节点 情况2：通过横叉边的后向边走到祖先节点 Tarjan算法求强连通分量(SCC)： 时间戳(timestamp)：根据深度优先遍历的顺序给每个点编号； 对每个点 ...

最近公共祖先(LCA问题)板子题： 例题：1172.祖孙询问 次小生成树应用： 例题：1171. 距离 树上差分应用： 例题：352. 闇の連鎖 三种方法如下：第二和第三种更实用一些 法一：向上标记法时间复杂度： 每次查询：最坏情况 O(n) 算法实现： x 向上走到根节点，并标记所有经过的节点 y 向上走到根节点，当第一次遇到已经标记的节点时，就找到了 LCA(x, y)。 法二：树上倍增法时间复杂度： 预处理：O(nlogn) 每次查询：O(logn) 算法实现： 预处理： 预处理数组 fa[i][j] ：表示从 i 开始，向上走 2^j 所能走到的节点。0 <= j <= logn。 如何预处理：dfs 或 bfs 都可以 若fa[i][j]的节点不存在，则令 fa[i][j] == 0。 当 j == 0时，fa[i][j] = i 的父节点 当 j > 0时，fa[i][j] = fa[fa[i][j - 1]][j - 1]，即、先跳到2^(j-1) 步，再跳 2^(j-1) 步 预处理数组 depth[i]：表示深度，或层数，规定根节点的深度为 ...

差分约束时间复杂度： 用最短路算法(spfa)实现 用途 求不等式组的可行解 如何求最大值和最小值 知识点如下； 差分约束如何建图： 首先明确，求最短路用 i <= j + x 来更新距离，含义为 j->i 边权为x，文字表示为i可用j来更新，求最长路用 i >= j + x 来更新距离，同理。 求最小值( >= x的最小值)，所有的不等式化为i >= j + x，添边:add(j, i, x)，求x0到每个点xi的最长路。 求最大值( <= x的最大值)，所有的不等式化为i <= j + x，添边为add(j, i, x)，求x0到每个点xi的最短路， 注意：若涉及区间和的问题，考虑前缀和，转化为两点之间的关系 例题：1169. 糖果代码如下：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787 ...

01分数规划例题：spfa求负环 + 01分数规划 可参考如下博客：分数规划 常见形式 (一堆和) / (一堆和) 使其结果最大 方法： 二分 [l, r] f的和 / t的和 > mid => f的和 > mid t的和 => (f[i] - mid t[i])的和 > 0 最终 等价于图中是否存在正环？ 代码如下：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include <iostream>#include <algorithm>#include <cstring>using namespace std;const int N = 1010, M = 5010;int n, m;int wf[N];int h[N] ...

SPFA求负环时间复杂度 O(km)，最坏O(nm) 两种方法： 法一：统计每个点入队的次数，如果某个点入队n次，则说明存在负环 法二：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数>=n，则说明存在负环 都是基于抽屉原理（鸽巢原理） 一般用法二，时间复杂度更低 常见问题： 为什么等价于将所有点入队？解释：建立虚拟源点，并将虚拟源点和其他所有点连一条边 为什么求负环时不需要将其他点初始化为正无穷？如果存在负环，则dist最终为-INF，所以dist无论时INF还是0无所谓，会绕负环无穷次，对于无穷而言具体的值就无所谓了。 关于TLE的优化 做题前要思考如何建图方便，因为spfa时间复杂度很危险，如何降低点和边的数量使关键 若时间复杂度接近O(nm)则可以默认其已经含有负环，具体可根据经验，(比如，当所有的入队次数超过2n时，我们就认为图中有很大可能时存在负环的)，缺点是不太稳定 将队列转化为栈，面对找负环的问题一般效率比较好，比上面的trick较稳定一些 代码如下：队列 + trick(小花招): 200ms + 1234567891011121314 ...

次小生成树例题：1148. 秘密的牛奶运输 定理：对于一张无向图，如果存在最小生成树和(严格)次小生成树，那么对于任何一棵最小生成树，都存在一棵(严格)次小生成树，使得着两棵树只有一条边不同 法一具体实现： 先求最小生成树，再枚举删去最小生成树中的边求解。 时间复杂度 O(mlogm + nm) 证明： 化零为整：把最小生成树与次小生成树得不同得一条边分为n-1类(1~n-1) 只需求出每一类得最小值，则一定可以求出次小生成树 弊端 求非严格次小生成树可以，但求严格次小生成树不太方便 法二具体实现 先求最小生成树，然后依次枚举非树边，将该边加入树中，同时从树中去掉一条边，使得最终得图仍然是一棵树。则一定可以求出次小生成树。 时间复杂度： 朴素算法 O(m + n^2 + mlogm)) lca 倍增优化 O(nlogn) 证明 声明： 设T为图G得一棵生成树，对于非树边a和树边b，插入边a，并删除边b的操作记为(+a,-b)。 如果T+a-b之后，仍然是一棵生成树，称(+a,-b)是T的一个可行交换。 由T进行一次可行变换所得到的新的生成树的集合称为T的邻集。 定理 ...

算法竞赛技巧防止最后卡空格(pta,,,)12for (int i = 1; i <= n; i ++ ) cout << v[i] << " \n"[i == n]; *str = “ \n”;解释: 当 i < n, cout << str[0]; ‘ ‘ 当 i == n, cout << str[1]; ‘\n’ 竞赛缓解压力及做题顺序 太紧张，可以吃一些东西，口香糖什么的，可以有效缓解压力 前两题较简单，看清题目，先做掉。 后面的题，若看很长时间了，仍然不会，打住！想暴力，那暴力分 防卡常 调用 函数库中的 clock()函数 clock()单位为 1e-6次方毫秒，1 clock() == 1e-6秒 例子代码:12345678910111213141516171819#include <iostream>#include <ctime>using namespace std;int main(){ int start = c ...

Kruskal算法时间复杂度： O(mlogm) 使用范围 求朴素最小生成树 求最小生成森林，(求最小生成树的前一半) 已知一些边，求最小生成树(求最小生成树的后一半) 具体实现： 将所有边按照权重从小到大排序 枚举每条边的顶点a, b, 权重c，若a, b不在一个集合，则合并a, b集合, 反之则跳过，判断下一条边 算法证明： 证明思路与prim算法类似。 如何证明这条边一定可以被选？ 假设不选当前边，最终得到了一棵树。然后将这条边加上，那么必然会形成一个环，在这个环上，一定可以找出一条长度不小于当前边的边，那么把当前边替换上去，结果一定不会变差。 证明结论：若该边的两点所在的集合不同，则该边必定在最小生成树中 证明结论如下： 反证法：假设没有选择该边x1，则必定选择了之后的边x2使得两集合合并，使之形成最小生成树 证明：把边x1加到用x2形成的最小生成树中，则会在形成一个环，且该边一定包含x1,x2，此时若把x2去除，则形成的也为一个生成树，且因为x1小于x2，新生成的生成树比原来的权值和还小，则可证x1比x2更合适，所以得证，若上述证明结论的情况发生，则必定成立！ ...

Prim算法时间复杂度： O(n^2 + m) 具体实现： 邻接矩阵存边的权值 距离初始化为正无穷 每次选择当前集合终和外界所连边的权值最小的点 将该边所连的点扩展，并用刚扩展的点更新其他点到当前集合的权值 算法证明： 证明思路与kruskal算法类似。 如何证明这条边一定可以被选？ 假设不选当前边，最终得到了一棵树。然后将这条边加上，那么必然会形成一个环，在这个环上，一定可以找出一条长度不小于当前边的边，那么把当前边替换上去，结果一定不会变差。 证明结论：当前与外界直接相连的权值最小的一条边，这条边一定可以出现在最优解中。 证明过程如下： 反证法：假设选择最小生成树的某一个状态集合x扩展某一个边x1(最小)时没有选择该边，选择了另一个边x2(非最小)，从而形成了一个生成树。 证明：已知集合x可扩展多个边x1, x2……x’等(权值升序排列)，选择了x2边扩展。若将x1边加入扩展了x2边而最终形成的生成树中，则必定会形成一个环，且该环上一定包含x’这条边，因为x1为扩展出来的权值最小的边，x’等其他边时扩展出来的非权值第一小边，则将x’去掉，x1加上，形成的还是一个生成树，且该 ...