最短路算法
$\mathbf{Floyd}$ 算法
思路简介
$Floyd$ 算法的思想本质是一个 $DP$ ，首先枚举中间点 $k$ ，对于每条路径
$i->j$ ，判断此路径若经过点 $k$
是否更优。状态转移方程为 $dis[i][j]=\min(dis[i][k]+dis[k][j],dis[i][j])$
$Floyd$ 算法枚举先中间点 $k$ ，再枚举路径起点 $i$ 和终点 $j$
，每层循环枚举次数都是 $n$ ，故算法时间复杂度为 $\Theta(V^3)$ 。
算法优劣
$Floyd$ 算法是最短路算法中唯一的一个多元最短路算法，在 $\Theta(V^3)$
的时间内可以求出任意两点的最短路。并且可以处理副边权，但不能处理负环。同时，由于时间复杂度较高，应用不是特别广。
$\mathbf{Dijkstra}$ 算法
思路简介
$Dijkstra$ 算法的思路是维护一个点集 $\mathbb{U}$
,点集内的点都是已经确定最短路的点。建立数组 $dis[]$
表示从源点出发到达每个点的最短路长度，每次从图中寻找离该集合最近的点 $v$
，并确定它的最短路长度 $dis[v]=dis[u]+w(u,v)$ （ $u$ 为点集中离 $v$
最近的点），然后将该点加入点集 $\mathbb{U}$ （也就是所谓的松弛操作）。\
$Dijkstra$ 算法需要进行 $n$
次松弛操作（每个点一次），每次松弛操作需要枚举所有点来寻找离点集最近的点，故算法时间复杂度为
$\Theta(V^2)$ 。\
考虑优化，我们需要在所有点中寻找离点集最近且不在点集中的点。换而言之，我们要在一个集合中寻找最小值。很容易联想到利用堆这种数据结构优化
$Dijkstra$ 算法。这样每次寻找最小值的时间复杂度降为 $\Theta(1)$
，每次加入点集后将相邻点插入堆中时间复杂度为 $\Theta(e\cdot \log_2 V)$ （ $e$
为该点边数），于是最后时间复杂度降为 $\Theta((V+E)\cdot \log_2 V)$ 。
算法优劣
$Dijkstra$ 算法是当前 $\mathcal{OI}$
中最主流的最短路算法，其应用范围广，基本不会被卡，但不能处理带负边权的情况。
$\mathbf{Bellman-Ford}$ 算法
思路简介
$Bellman-Ford$ 算法最初的思路仍然像一个 $DP$ ，数组 $dis[i][j]$
代表从源点出发经过最多 $j$ 条边到达 $i$
点的最短路长度。状态转移方程显然$dis[i][j]=\min(dis[i][j-1],\min\left\{dis[k][j-1]+w(i,k)\right\})$
考虑对每个点的松弛操作改为对每条边进行松弛操作，每轮松弛操作中对每条边
$u-v$ 都进行一次松弛 $dis[v]=\min(dis[v],dis[u]+w(u,v))$ , $n-1$
轮松弛后即可得出源点到每个点的最短路。如果接下来还能对边进行松弛，则说明图中存在负环，最短路为负无穷。因为没有负环的图中最短路最多经过
$n-1$ 条边（每个点经过一次），如果一条最短路经过了多余 $n-1$
条边，则此图必定有负环。由上述思路，经过 $n-1$ 轮松弛，每轮松弛 $m$
条边，时间复杂度为 $\Theta(V\cdot E)$ 。
算法优劣
$Bellman-Ford$
算法可以在有负边权的图中找出最短路，并且可以判断图中有没有负环。其时间复杂度与边数有关，在稀疏图中表现优异，但在稠密图中（边数在
$1e6$ 左右）就会被卡。
$\mathbf{SPFA}$ 算法
思路简介
$SPFA$ 算法的全称是 $Shortest\quad Path\quad Faster\quad Algorithm$ ，其本质是
$Bellman-Ford$
的队列优化。首先把起点入队，同时标记入队，然后重复以下操作直到队列为空：\
-取出队首并标记出队。\
-遍历与其相连的边，进行松弛操作。\
-如果与其相连的点没有在队列中，就将其入队，并标记。\
如果有一个点入队次数超过 $n-1$ ，即代表有边被松弛超过 $n-1$
次，说明图中有负环。考虑每个点都入队 $n-1$ 次，这种情况就和朴素的
$Bellman-Ford$ 算法时间复杂度一致，为 $\Theta(V\cdot E)$ 。
算法优劣
$SPFA$ 曾一度被证明复杂度为 $\Theta(k\cdot E)$ （其中 $k$
为小常数），后证明此复杂度是错误的，所以 $SPFA$ 曾一度被卡。后有 $LLL$
， $mcfx$ 优化， $SLF$ ， $SLF$带容错， $SLF-swap$
，等一系列神仙优化，但最终还是可以被卡掉。但 $SPFA$
可以在随机数据的情况下更快判断负环，弥补的 $Dijkstra$
算法不能处理负环，负边权的缺陷。
最小生成树算法
$\mathbf{Prim}$ 算法
思路简介
同 $Dijkstra$ 算法一样， $Prim$
算法的思路是也维护一个点集，点集内的点都是已经在最小生成树上的点。每次从图中寻找离该集合最近的点
$v$ ，加入集合，并将边 $e(u,v)$ （ $u$ 为点集中离 $v$
最近的点）加入最小生成树。同 $Dijkstra$ 算法一样， $Prim$
算法的时间复杂度也是 $\Theta(V^2)$ 。同理，也可以用堆优化至
$\Theta((V+E)\cdot \log_2 V)$
算法优劣
从时间复杂度的角度看，朴素的 $Prim$
算法与边数完全无关，适用于稠密图。优化后主要也是与点数有关。总体来看，
$Prim$ 算法适用于稠密图。
$\mathbf{Kruskal}$ 算法
思路简介
$Kruskal$
算法使用的数据结构”并查集”，它的思路是把边从小到大排序，然后对每条边检查两个端点是否在一个并查集中，若不在一个并查集中，则将其合并，将该边加入最小生成树，直到加入
$n-1$
条边后终止。时间复杂度为排序的时间加上对每条边进行判断，合并的时间，均摊时间复杂度为
$\Theta(E\cdot \log_2 E)$ 。
算法优劣
于上文的 $Prim$ 算法相比， $Kruskal$
算法复杂度只于边数有关，适用于稀疏图，同样也是最主流的最小生成树算法。
有向图算法
拓扑排序
拓扑排序是在有向图中寻找一个可行的拓扑序，使得每个点的前驱在该序列中都在这个点的前面。考虑朴素做法，循环
$n$ 次，每次找到一个没有在序列答案序列中且入度为 $0$
的点，把它连出的边的每一个终点入度 $-1$
，然后加入答案。此做法时间复杂度易得为 $\Theta(V^2)$ 。\
考虑优化。首先建立一个队列，把图中入度为 $0$
的点入队。然后把队首弹出，放入答案序列，并且把该点连出的边的每一个终点入度
$-1$ ，同时把入度为 $0$
的终点加入队列，重复此过程直到队列为空。如果答案序列长度不足 $n$
,则证明该有向图有环。此做法的时间复杂度为 $\Theta(V+E)$ 。
$\mathbf{Tarjan}$ 算法
$Tarjan$
算法是有向图的终极算法，有向图中可用于求强连通分量，还能缩点。具体思路是利用
$dfs$ 序的性质，在 $dfs$ 回溯是进行求解。首先建立数组 $dfn[],
low[]$ ，分别代表 $dfs$ 序和 $dfs$ 序中可以回溯到的最早位置。在
$dfs$ 的时候处理出两个数组，就可以利用 $dfs$
序的性质求解。这样每个点，每条边都仅访问一次，时间复杂度为 $\Theta(V+E)$
。
求强连通分量
显然，在 $dfs$
序中，如果子孙能有一条边连向祖先，那么从祖先到这个子孙之间的所有点都在一个强连通图中。当一个点能够回溯到的最早位置为自己，即
$dfn[u]=low[u]$
时，这个点以及可以回溯到它的最后子孙之间的点就处于一个强连通分量中。此时可以想到使用栈来处理。建立一个栈，
$dfs$
时将点压入其中，然后当回溯到一个点，找到强连通分量后就将这之间的点全部弹出，然后放入同一个强连通分量中。
缩点
同上，将一个强连通分量缩成新图中的一个点即可。接下来按题目要求在 $DAG$
上操作。
无向图算法
$\mathbf{Tarjan}$ 算法
你没有看错！又是它！无向图中， $Tarjan$
算法可以用来求双连通分量，割点，桥。思路和有向图差不多，时间复杂度也一致。
割点
割点指的是去掉这个点对图的连通性有影响。考虑一个点如果是割点，那么它的所有子孙能够回溯到的最早位置一定都是自己的子孙，即对于所有子孙
$v$ ,都有 $low[v]>=dfn[u]$ 。
桥
与割点类似，桥指的是去掉这条边后对图的连通性有影响。同上理，如果一个点对于所有子孙
$v$ ,都有 $low[v]>dfn[u]$ ，那么边 $e(u,v)$ 为桥。
点双连通分量
无向图中，没有割点的一个极大连通分量就是一个点双连通分量，求法与割点类似。
边双连通分量
同理，无向图中，没有桥的一个极大连通分量就是一个边双连通分量，求法与桥类似。
二分图
匈牙利算法
如果一个图中所有点可以被分成两个非空点集 $\mathbb{U}$ ， $\mathbb{V}$
，且 $\mathbb{U}\cap \mathbb{V}=\varnothing$
，其中同一属于点集中的点不互相连边，那么这个图就是二分图。\
任意两条边都没有公共顶点的一个边集称为二分图的一组匹配。包含边数最多的一组匹配称为二分图最大匹配。求解二分图最大匹配，可以用匈牙利算法。\
一组匹配 $\mathbb{E}$ ，对于任意一条边 $e$ ，若 $e\in \mathbb{E}$ 则称
$e$ 为匹配边，否则称 $e$
为非匹配边。所有匹配边的两个端点都称为匹配点，其余点称为非匹配点。\
匈牙利算法的思路是在图中寻找增广路，增广路是指的一条从非匹配点到非匹配点的路径，其中匹配边与非匹配边在路径上交替出现。增广路在对路径上所有边取反（匹配边变成非匹配边，非匹配边变成匹配边），可以使匹配边条数
$+1$ 。\
匈牙利算法寻找增广路的方法是依次尝试给每一个结点 $u\in \mathbb{U}$
寻找一个匹配的结点 $v\in \mathbb{V}$ ，其中 $v$ 满足以下条件之一：
- $v$ 是非匹配点。
- $v$ 已经与 $u’$ 匹配，但 $u’$ 可以找到另一个点 $v’$ 与之匹配。\
对于每个点都要进行一次匹配，每次匹配的最坏情况是遍历所有的边，所以时间复杂度为
$\Theta(V\cdot E)$ 。
网络流
一个网络指的是一张有向图
$\mathbf{G}=(\mathbb{V},\mathbb{E})$，每条边的权值称为边的容量。图中还有两个特殊结点
$s$ ， $t$ ，称为源点和汇点。定义流量 $f(u,v)$
为实数函数，且满足以下条件：\
-对于每条边 $e(u,v)\in \mathbb{E}$，都有 $f(u,v)\leq w(u,v)$ 。\
-取 $\forall x\in \mathbb{V},x\neq s,x\neq t$ ，都有
$\sum_{e(u,x)\in \mathbb{E}} f(u,x)=\sum_{e(x,v)\in \mathbb{E}} f(x,v)$
。\
-对于任意流量 $f(u,v)$ ，都有 $f(u,v)=-f(v,u)$ 。\
对于一条边 $e(u,v)\in \mathbb{E}$ ， $w(u,v)-f(u,v)$
就是这条边的残量。一个网络中所有残量组成的新的网络称为残量网络。\
网络的流量就是指的 $f(s,t)$ 。一个网络最大的合法流量称为网络最大流。
$\mathbf{EK}$ 算法
思路简介
求解网络最大流，一种方法是用 $EK$ 算法求解。 $EK$
算法的思路与匈牙利算法差不多，也是通过寻找增广路。此时增广路的定义为一条残量均大于
$0$ 的路径。具体操作为从 $s$ 开始向外 $bfs$ 只走残量大于 $0$
的边，直到找到 $t$ 为止。然后计算最小残量 $minf$ ，把增广路上的边边权
$-minf$ ，然后把反向边边权 $+minf$ 直到找不到增广路。此算法时间复杂度
$\Theta(V\cdot E^2)$
算法优劣
此算法虽然时间复杂度较高，但很难跑满。一般在稀疏图中跑网络流会用 $EK$
算法。
$\mathbf{Dinic}$ 算法
思路简介
更多的时候，求解网络流会用 $Dinic$ 算法。 $Dinic$ 算法的主要特点是对图用
$bfs$ 进行分层，再用 $dfs$
寻找增广路，每次寻找增广路的时候只往下一层找，保证了 $dfs$
的迭代次数不多。同时还可以加入各种剪枝。朴素的 $Dinic$ 算法时间复杂度为
$\Theta(V^2\cdot E)$ 。
算法优劣
乍一看，此算法时间复杂度和 $EK$
算法差不多，但实际应用中一般处理的都是稠密图，边数远大于点数，此时用
$Dinic$ 是一个不错的选择。
其他建图问题
差分约束系统
一个由 $n$ 个变量和 $m$ 个形如 $a_i-a_j\leq k$
的约束条件组成的系统称为差分约束系统。可以将约束条件转化为形如
$dis[i]\leq dis[j]+w(i,j)$ 的图论条件。\
显而易见，可以转化为图论问题。对于每个条件 $i+j\leq k$ ，建立一条边
$w(i,j)=k$ 。新建虚拟源点，源点连向所有点的边权为 $0$
.在图上跑最短路，最终 $dis[]$ 即为一组可行解。
$\mathbf{2-sat}$ 问题
$2-sat$ 问题是一种特殊的逻辑判断问题。给定 $n$ 个变量和 $m$
个限制条件，每个变量有一个值 $val_i\in\left\{0,1\right\}$
，且限制条件均为形如\
$(\neg)val_i(opt)(\neg)val_j$
等对两个变量的值的限制。由于每个变量都只有两个状态，所以考虑建图是把一个变量
$val_i$ 拆成两个点 $i$ ， $i’$ ，分别表示这个点取 $0$ 还是取 $1$
，然后考虑连边。每条边 $e(u,v)$ 表示如果点 $u$ 选择的那么就必须选 $v$
。最后可以发现，如果选择了一个点，那么也要选择和它在同一个强连通分量里的点。所以我们可以通过判断对于每个变量
$val_i$ ， $i$ 和 $i’$ 是否在同一个强连通分量里。如果是，那么这个
$2-sat$ 问题就无解，否则就可以输出 $i$ 和 $i’$
中拓扑序较大的一个形成一组解。连边的方式主要有以下几种：
- $val_i\oplus val_j=1$ 即 $i$ ， $j$
必须选一个但不能同时选。连边方式为 $i->j’,j->i’$ 。 - $val_i\oplus val_j=0$ 即 $i$ ， $j$ 要么都选要么都不选。连边方式为
$i->j,j->i,i’->j’,j’->i’$ 。 - $val_i|val_j=1$ 即 $i$ ， $j$ 至少选一个。连边方式为 $i’->j,j’->i$
。 - $i$ 即 $i$ 必须选。连边方式为 $i’->i$ 。
- $\neg i$ 即 $i$ 不能选。连边方式为 $i->i’$ 。\
此方法每条边都至多经过一次，故时间复杂度为 $\Theta(E)$ 。