最小树形图 / 朱刘算法
前置定义树形图：在一个有向图中，满足存在一个入度为 $0$ 的点，除了该点入读均为 $1$，且该图不存在环，那么称为树形图。 最小树形图：给定有向边权图，求以某点为根的边权和最小的子图，满足该子图为树形图。朱刘算法模板链接 相当于是一种贪心的思想。 首先我们发现一个合法的树形图中除根外的每个点只有一条入边，所以我们就贪心的选择原图中所有入边中最小的。但是注意到这样选出来的子图可能会存在环，所...
前置定义树形图：在一个有向图中，满足存在一个入度为 $0$ 的点，除了该点入读均为 $1$，且该图不存在环，那么称为树形图。 最小树形图：给定有向边权图，求以某点为根的边权和最小的子图，满足该子图为树形图。朱刘算法模板链接 相当于是一种贪心的思想。 首先我们发现一个合法的树形图中除根外的每个点只有一条入边，所以我们就贪心的选择原图中所有入边中最小的。但是注意到这样选出来的子图可能会存在环，所...
UPD：狄利克雷卷积的单位元表示符号建议使用 $\epsilon$。积性函数定义对于一个函数 $f$，若有 $\forall x,y,(x,y)=1,f(xy) = f(x)*f(y)$，则我们称这样的函数为积性函数。 举例：$\phi(x),\mu(i),d_k(n)$（$n$ 的所有正因子 $k$ 次幂和）性质若 $f(x)$ 为积性函数。 设 $n = \Pi p_i^{q_i}$，则...
题目链接题目简述给定 $N$ 个点 $M$ 条边的无向图，每条边有两个权值 $a$ 与 $b$ 。求一条 $1$ 到 $n$ 的路径使得路径经过边的最大 $a$ 与最大 $b$ 的和最小。无法到达输出 $-1$。$ n \leq 50000,m \leq 100000$。解题报告乱入：这个题目只需要枚举 a 然后动态加边跑 SPFA 就可以了。 请不要用一个时间复杂度是 $O(nm)$ 的算...
定义链剖分首先我们知道，OI 中能见到的有重链剖分，实链剖分和长链剖分。 重链剖分已经在之前的树链剖分中熟练运用过了，长链剖分不常考，所以这次我们先来看一看实链剖分。 实链剖分：将某一个儿子的连边划分为实边，而连向其他子树的边划分为虚边。 我们发现边的虚实是可以动态变化的，因此可以使用更高级、更灵活的 Splay 来维护每一条由若干实边连接而成的实链，基于这个原理，LCT 才能解决很多的动态...
Stoer Wagner 算法主要是解决无向图最小割的问题。题目链接给定一张无向图，每一条边都有其花费，求最少能使这张图不连通应割掉的边数。 原作者论文，侵删解题思路首先我们可以使用网络流暴力跑，也就是随机一个源点然后枚举汇点跑最大流那种，但是时间复杂度有点高，上界是 $O(n^3m)$。于是 就有了 Stoer Wagner 算法来解决这个问题。我们先描述一下这个算法的一般流程： 1. $...