原文oi wiki:二分图 二分图，又称二部图，是一类结构特殊的图。它的顶点集可以划分为两个互不相交的子集，使得图中的每条边都连接这两个集合之间的一对点，而不会连接同一集合内部的点。

得益于这种简单的结构，二分图不仅展现出许多优雅的性质，也广泛应用于现实生活中的建模场景，例如任务分配、推荐系统、匹配市场等。许多在一般图上困难的优化问题，在二分图上都可以高效、准确地求解。

模版

瞎扯:我觉得这个部分的图论挺有意思的所以多写了一点XD 树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。

具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。

树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作「实链剖分」），大多数情况下（没有特别说明时），「树链剖分」都指「重链剖分」。 原文oi wiki:树链剖分

启发式算法是什么呢？ 启发式算法是基于人类的经验和直观感觉，对一些算法的优化。 说白了,用思维去强行干碎(不是)复杂度

树上启发式合并

原文oi wiki:dsu-on-tree 我们考虑树上的离线问题或者是其他情况可以从树上dp的角度去思考：

例题

例题1 例题2

CA(Lowest Common Ancestor) cover: icon: editLink: false order: 4 author: badb0ttle date: 2025-8-26 category:

• 算法 tag:
• 图论

此页面会在文章列表置顶

sticky: false star: false footer: 图论

---

LCA

原文oi wiki:最近公共祖先 两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。 为了方便，我们记某点集 S=$\{v_1,v_2,\ldots,v_n\}$ 的最近公共祖先为 $\text{LCA}(v_1,v_2,\ldots,v_n)$ 或 $\text{LCA}(S)$。 特殊性质:LCA(l,l+1,l+2,...,r)=LCA(dfs序最小,dfs最大)

最小生成树

原文oi wiki:MST

方法

1.Kruskal(按边)
2.Prim(按点)

1.Kruskal

思路很简单，为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了n-1条边，即形成了一棵树。 时间复杂度 O(nlog(n)) code:

原文oi wiki:SDC

差分约束系统是一种特殊的 $n$ 元一次不等式组，它包含 $n$ 个变量 $x_1, x_2, \dots, x_n$ 以及 $m$ 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 $x_i - x_j \leq c_k$，其中 $1 \leq i, j \leq n, i \neq j, 1 \leq k \leq m$ 并且 $c_k$ 是常数（可以是非负数，也可以是负数）。

最短路径

原文oi wiki:SP

基础

1.Dijkstra
2.Floyd

1.Dijkstra

用于求 单源最短路径，只能处理非负权边。其核心思想是： 每次从未确定的点中选择当前距离源点最近的点加入集合，并用它来更新其他点的最短距离。 原理十分简单，大学课堂100%讲过 堆优化 Dijkstra 时间复杂度为 O((n + m)log n),适用于稀疏图