图论一家子

0. 存图

可以用邻接表来对每个点存出边，也可以用链式前向星。

链式前向星给了每条边一个标号，并且若用 0-index，则边 $i$ 的反边是 $i \oplus 1$ ，在网络流等场景中很好用。

但是还有一个方法，记录每个点的出度后做前缀和，然后将 $u$ 每条出边放在 $[d _ u,d _ {u + 1})$ 上，这样内存连续，访问非常快。

写出来是这样的：

1
int n,m,u[MAXM],v[MAXM],d[MAXN],g[MAXN];
2
inline void initGraph()
3
{
4
    for(int i = 1;i <= m;i++)
5
    {
6
        cin >> u[i] >> v[i];
7
        ++d[u[i]];
8
    }
9
    for(int i = 1;i <= n;i++)
10
        d[i + 1] += d[i];
11
    for(int i = 1;i <= m;i++)
12
        g[--d[u[i]]] = v[i];
13
}

遍历出边是这样的：

1
for(int i = d[u];i < d[u + 1];i++)
2
    // Do Something

经实测，这样的运行时间是用 vector 存图的约 $\frac{3}{4}$ ，并且还有卡常空间。

1. 最短路

不懂原理去找别的文章↗看。

SPFA 尽量不要拿来求最短路，求负环可以用 DFS 实现的 SPFA。

DFS SPFA 的主要思想就是能更新最短路的才去跑，如果在一条路径上遇到了同一个被访问过的点就有负环，时间复杂度不卡能做到 $\Omicron(E)$ ，如果要拿来求最短路还是算了。贴个代码。

一般卡了 BFS SPFA 的卡不了这个，但是不排除出题人两个一起卡，所以尽量只在差分约束这种近似随机图里用。

1
inline bool SPFA(int u)
2
{
3
    vis[u] = 1;
4
    for(auto [v,w] : g[u])
5
    {
6
        if(dis[v] > dis[u] + w)
7
        {
8
            dis[v] = dis[u] + w;
9
            if(!vis[v])
10
            {
11
                if(SPFA(v))
12
                    return 1;
13
            }
14
            else
15
                return 1;
16
        }
17
    }
18
    return 0;
19
}

但如果硬要用 SPFA 求最短路，我建议加上容错 SLF 和 mcfx 优化，容错 SLF 就是使用双端队列代替队列，定义一个容错值 $x$ ，一般取 $\sqrt{\sum w}$ ，若 $u$ 的距离大于队首元素距离加 $x$ 则插入队尾，否则插入队首，而 mcfx 优化就是当入队次数在 $[L,R]$ 间时从队首插入，否则从队尾插入，一般取 $L = 2,R = \sqrt{n}$ 。

Dijkstra 可以用 ZKW 线段树来代替优先队列，如果可以的话将 $(dis _ u,u)$ 压成一个 long long，这样会快很多。

允许 $k$ 次免边权或者改为特定边权考虑分层图最短路。

差分约束

直接并入了懒得再开一节。

就是有一些类似 $x _ v \le x _ u + w$ 的限制，发现这个和三角不等式 $dis _ v \le dis _ u + w$ 很像，所以我们建边 $u \xrightarrow{w} v$ 。

大于等于或者等于可以变形为小于等于，所以直接跑最短路 SPFA，如果出现负环则无解，否则 $dis$ 为一组合法解。

建议像上面那样加几个优化防止被卡。

同余最短路

~~虽然同余最短路写最短路就好比玩游戏玩原神，但是我真玩原神~~

和上面差分约束的思想很像，都是把数学问题转为图论问题。一般是设 $f(i)$ 为在模 $x$ 意义下，一些值之和的最小值。显然，有 $f(i) + y \ge f((i + y) \bmod x)$ ，很像三角不等式，所以一样的我们可以跑最短路求出这个 $f(i)$ ，又因为 $f(i)$ 合法，则 $f(i) + kx$ 显然也合法，然后再根据题意计算贡献。

2. 最小生成树

Kruskal 和 Prim 比较简单，着重来看 Boruvka。

主要思想就是一开始将每个点视为一个连通块，在每一轮循环中，找到每一个连通块的最小边（就是边权最小的边），然后合并每条最小边两端的连通块。

其实难点就是用一个可以接受的复杂度来找到最小边，为此可能需要某些 DS 或者跑 DP。

Kruskal 重构树

本质是把 Kruskal 求生成树的过程构造成一棵树的二叉树。

具体的就是在 Kruskal 中每加一条边就新建一个点，将这个点的两个儿子设定为两个连通块的根结点。所以若求的是最小生成树就是大根堆，否则就是小根堆。

有个非常强大的性质，原图中两点间的所有路径上的最小值等于 Kruskal 重构树上两点 LCA 的点权，并且对于新点，这个点子树中的叶子都能只走边权 $\le x$ 的边互相到达。

只走边权 $\le x$ 的边到达 $u$ 的点可以用倍增来求出，找到 Kruskal 重构树上最浅的点满足点权 $\le x$ ，子树内的点都可以只走边权 $\le x$ 的点到达 $u$ 。

3. 欧拉路径 / 欧拉回路

欧拉路径的定义就是从起点出发，经过每条边恰好一次，到达终点的路径，若起点等于终点就是欧拉回路。

对于无向图，若存在欧拉路径，则只能有 $0$ 个或者 $2$ 个点的度数为奇数，其他的点的度数必须是偶数，若是欧拉回路，则只能有 $0$ 个奇点。对于有向图，则只能有 $0$ 个或 $2$ 个点的入度与出度不同，如果为 $2$ 个，则有一个点出度比入度大 $1$ ，这个点是起点；有一个点入度比出度大 $1$ ，这个点是终点，如果为 $0$ 则是欧拉回路。

然后构造欧拉路径就很简单了，从起点开始，直接遍历每条边就行，跑完每条边把自己加进一个栈里，最后输出栈里面的元素就行。

4. 连通性相关

强连通分量

就是图的一个子集，使得对于子集中的任意两个点均可互达。

对于一张图，我们求出它的一棵 DFS 生成树，则我们有下面几种边：

树边：DFS 生成树中的边
回边：连接一个点与其祖先的非树边
横叉边：连接一个点与其非祖先结点的非树边
前向边：连接一个点与其子树中的点的非树边

我们维护一个栈，然后跑 DFS，每次新加入一个点就放进栈里，然后维护以下两个数组：

$dfn _ u$ ， $u$ 的 DFS 序
$low _ u$ ， $u$ 能走到的在栈中的结点的最小 DFS 序

走到一个点 $u$ 后，我们对每个邻居 $v$ 做以下事情：

若未搜索过 $v$ ，则搜索 $v$ ，并且用 $low _ v$ 更新 $low _ u$ ，因为 $v$ 能到的点 $u$ 也能到。
若搜索过 $v$ ，且 $v$ 在栈中，则用 $dfn _ v$ 更新 $low _ u$
若搜索过 $v$ ，且 $v$ 不在栈中，就不用管了，因为已经搜完了

$u$ 处理完后，若 $dfn _ u = low _ u$ ，则说明 $u$ 是一个强连通分量的根，在栈中它及上方所有点构成一个 SCC。

点双连通分量 & 割点

以下内容中 $low _ u$ 表示 $u$ 不经过父亲能走到的最小的 DFS 序。

点双连通分量：对于一个点双连通分量中任意两个点 $u,v$ ，删去任意一个除 $u,v$ 以外的点仍然连通。

割点：删去该点后使得连通块个数增加。

首先我们还是考虑用上面的 $dfn _ u$ 与 $low _ u$ ，若对于一个点 $u$ 的一个邻居 $v$ ，有 $low _ v \ge dfn _ u$ ，则这个点可能是割点。具体来讲就是如果这个点是根结点，则需要子结点个数大于 $1$ ，其他的点满足上述条件则一定是割点。

然后考虑怎么求点双连通分量，其实也很简单，点双在 DFS 生成树上的 DFS 序最小的结点一定是根结点或割点。所以找到割点之后，割点与栈中子结点上方的所有点构成一个点双，需要注意的是一个割点可能会出现在多个点双中，所以不能弹出割点。

边双连通分量 & 割边

边双连通分量：对于一个边双连通分量中任意两个点 $u,v$ ，删去任意一条边后对于任意 $u,v$ 仍然连通。

割边：删去该边后使得连通块个数增加。

无重边情况下求割边比较简单，若对于一条边 $(u,v)$ 有 $low _ v \gt dfn _ u$ 则说明 $(u,v)$ 是一条割边。而对于有重边的情况，我们更新 $low$ 时不用来时的边更新就行，为此可以用链式前向星存图。

边双连通分量等价于在无向图中求强连通分量，只不过不用记录是否在栈中，不用父亲结点更新就行了。

圆方树

这东西应该叫广义圆方树？

狭义圆方树只能拿来处理仙人掌上的问题，不如写广义圆方树，区别是狭义圆方树只把环建成方点，而广义圆方树会把每个点双建成方点，包括两点一线。

具体的就是跑点双 Tarjan，然后找到一个点双就建一个方点，点双上所有点向方点连边，设发现点双的那个点为 $u$ ，则我们设方点的父亲是 $u$ ，边权为零元，其他点连到方点的边权为自己到 $u$ 的两条路径中权值更优的那个。以最短路为例，其他点到方点的距离设为自己到 $u$ 的最短路长度。

然后考虑询问，还是以最短路为例，我们求出 $p = \text{LCA}(u,v)$ ，若 $p$ 为圆点，则直接当在树上一样算就行，但是如果在一个方点，我们就要考虑最后一步怎么走，找到 $u \to p$ 上的 $p$ 的儿子 $son _ u$ ， $v \to p$ 上的儿子 $son _ v$ ，答案为 $u \to son _ u$ ， $v \to son _ v$ ， $son _ u \to son _ v$ 的距离之和，其中 $son _ u \to son _ v$ 的距离定义为在这个点双上两点间的最短路。

5. 网络流

网络就是一个有向图，其中有两个特殊的点源点和汇点，边有一个特殊的权值叫做容量，可能附有权值，表示每有 $1$ 流量需要这么多的代价。

流 $f(u,v)$ 满足大小不超过每条边的容量，即 $f(u,v) \le c(u,v)$ ，且每个结点净流量为 $0$ 。

最大流 / 最小割

懒得学其他的所以只写 Dinic。

实质是一个反悔贪心，基础是一个叫 Ford-Fulkerson 增广（以下简称 FF 增广或者直接叫增广）的东西，我们对每条边 $u \xrightarrow{c} v$ ，建一条反向边，初始容量为 $0$ ，拓展一下流的定义，规定 $f(v,u) = -f(u,v)$ ，其中 $u \to v$ 是一条存在的边。一条增广路表示从源点出发，到达汇点的流。引入负流之后，我们就可以通过一直找增广路直到找不到为止，这个时候就有总流量等于最大流。因为引入了负流，所以可以支持反悔操作，表现为先取局部最优解后，再次取局部最优解依然能够得到全局最优解。

但是每次只找一条增广路还是太慢了，我们可以给原图分层，规定一条边只能从层数低的流向层数高的，这样就能避免许多不必要的增广。然后我们找增广路，直到找不到为止。实现上，分层可以用 BFS 来实现，然后用 DFS 找出 BFS 生成树中一个结点的子树的所有增广路。时间复杂度上限是 $\Omicron(n ^ 2 m)$ ，但是远远跑不满，所以网络流复杂度一般是玄学。但是对于特定的图，比如二分图，复杂度是 $\Omicron(n \sqrt{m})$ 的。

有个定理叫最大流最小割定理，就是最大流等于最小割。

最小 / 最大费用最大流

就是满足最大流的前提下保证最小费用，你把分层用的 BFS 换成 SPFA 就行了。时间复杂度上界是 $\Omicron(nmf)$ ， $f$ 是最大流。一般不会被卡，被卡了找性质或者写 Primal-Duel，但是我不会。

6. 二分图

判定

二分图等价于一张图可以被黑白染色，且一条边两端的颜色不同。

对于一个连通块，以任意颜色开始，对每个结点染色，遇到一条边染成异色，如果已经被染色就检查是否异色，否则不是二分图。

如果是动态加边情况，则用扩展域并查集，一个点 $u$ ，拆成 $u _ 1,u _ 2$ ，表示 $u$ 为白色与 $u$ 为黑色。连边 $(u,v)$ 时，在并查集上合并 $(u _ 1,v _ 2)$ 和 $(u _ 2,v _ 1)$ ，如果任意 $u _ 1,u _ 2$ 在同一集合里就不是二分图。

最大匹配

我不会匈牙利算法，所以只写网络流。

我们新建源点和汇点，从源点向左部点连容量为 $1$ 的边，中间的边从左边连向右边，容量为 $1$ ，右边的点连向汇点，容量为 $1$ ，跑最大流，最后最大流就是最大匹配。

最大权匹配

给上面新加的边赋边权为 $0$ ，中间的边该是什么是什么，然后跑最大费用最大流，最后费用就是答案。

不会真的考 KM 吧，不会吧不会吧不会吧。

7. 平面图

平面图就是可以放在平面里且每条边不交的图，平面图的对偶图就是将被分割的每个平面视作一个点，对于每条边，连接两侧平面所代表的点，边权就是原边权。

有个性质，平面图的最小割等于对偶图的最短路。

8. 树论

DFS 序

DFS 过程中访问结点的顺序，满足一个子树中的结点 DFS 序连续。

树链剖分

就是对每个结点找到子树最大的儿子，称为重儿子，重儿子串成的链称作重链，然后做 DFS 序，使得满足 DFS 序的性质前提下重链上的 DFS 序连续。这样就把树的结构拍到了序列上，然后用 DS 维护就行了。重链的性质是任意一条路径都可以用 $\Omicron(\log n)$ 条重链拼成。

启发式合并

还是用上面重儿子的定义。我们处理某一类信息的时候，可以直接利用重儿子的信息，加入自己的信息之后合并轻儿子的信息，具体的可以开个内存池，然后给每个结点分配一个指针，父亲直接复用重儿子的指针，然后合并轻儿子信息。

lxl 把这个和树链剖分统称为静态链分治。

长链剖分

把重儿子的定义换成了深度最大的子结点。

一般拿来优化和深度有关的 DP，实现上就和上面一样，直接继承重儿子指针。

点分治 / 点分树

特征是和路径、点对等东西相关，实现上就是每一层分治都找出重心，然后考虑怎么合并子树路径信息。

点分树就是把结构定了下来，多了树高是 $\Omicron(\log n)$ 的性质，然后用数据结构直接支持查询。修改对每个祖先都更新，可能需要容斥。

Thanks for reading!