图论

· · 个人记录

笔者开始复习图论了！于是就有了这篇 blog。

最短路

单源最短路径问题，即求解从起点 s 出发，到图上任意一点的距离。求解单源最短路可以使用 Dijkstra 或者 SPFA 算法。

Dijkstra 利用贪心思想，每次取出未被标记、距离最小的点然后松弛该点的所有出边。在稠密图上，我们直接使用O(n^2)的朴素算法即可, 在稀疏图上利用二叉堆对寻找全局最小值的过程进行优化，时间复杂度 O(m~log~m)。

由于 Dijkstra 的贪心性质，该算法只适用于边全均非负的情况。同时，在负权图上，我们可以利用特殊构造方式，让节点不断被重新松弛，从而让 Dijkstra 的时间复杂度退化到指数级别。

Bellman-Ford 基于迭代思想，通过扫描所有边，不断对节点进行松弛，让所有边都满足三角形不等式，时间复杂度 O(nm)。

SPFA 算法通过队列对 Bellman-Ford 进行优化，把待扩展的节点保存在队列内，避免了对无用节点的扫描，在随机图上复杂度为 O(km) 级别，但是在特殊构造的图上可能退化为 O(nm)。

值得一提，在负权图上这两种算法也能正常运作。

另外，在图上进行动态规划时，可能会遇到环形依赖，即图不是一张 DAG。通常情况下有两个解决办法：

· 利用 Dijkstra 的贪心思想，即状态之间转移时，代价都是正的，所以能把目前队列中的最小代价的状态确定为一个最优状态。换句话说，Dijkstra 是在“有单调性的图上”，利用单调性可以确定出一个拓扑序，按照这个序列进行转移就能得到正确答案。

· 借助 SPFA 算法进行动态规划，即在这张图上多次迭代，最后把答案收敛出来。

习题：

P1875 佳佳的魔法药水 最短路扩展 + 最短路计数

P4042 [AHOI2014/JSOI2014] 骑士游戏 最短路扩展

P1462 通往奥格瑞玛的道路 二分答案最短路

最短路树是原图的一棵生成树，通常以起点 s 为根。

对于任意点 x，树上 s 到 x 的距离等于 s 到 x 的最短路。

建图：求解最短路的过程中，保留最后一次松弛点 u 的边 (u,v)。

对于任意节点 x，最短路 DAG 中包含所有起点 s 到 x 最短路经过的边。

最短路 DAG 是有向无环图。若存在环，则说明原图中存在负环或 0 环，此时不存在最短路 DAG。

最短路 DAG 的每一棵生成树都是最短路树，所有最短路树都是最短路 DAG 的生成树。

建图：求出最短路后, 遍历所有边 (u,v), 若 dis_{v} = dis_{u} + w_{u,v} 则保留这条边。

对于非严格次短路，图中存在一条以上最短路时，非严格次短路就是最短路；否则非严格次短路就是严格次短路。

类似用 dijkstra 算法求解最短路的过程，我们可以用两个数组 dis_{0,x} 和 dis_{1,x} 分别记录起点到节点 x 的最短路和严格次短路。

如果图中不存在非正环，那么任意一条次短路至多经过一个点两次。 所以我们同样可以用 vis 数组记录一个点被扩展的次数，并跳过经过两次以上的节点。

另外一种做法是，在原图和反图上求解单源最短路，得到每个节点到起点 s 和终点 t 的最短距离。

由于严格次短路至少有一条边与最短路不同，我们可以枚举不在最短路上的边 (u,v)，\min dis_{s,u}+w_{u,v}+dis_{v,t} 即为所求。

习题：

P2865 [USACO06NOV] Roadblocks G

P2829 大逃离

当我们需要额外的信息来维护最短路的时候，我们可以考虑使用分层图最短路。

中心思想：建立多层图，同层之间正常连接，不同层之间用优惠边权连接，然后求解最短路。

众所周知，动态规划对状态空间的遍历构成一张有向无环图，这说明分层图问题从 DP 角度看其实是二维 DP 问题。

习题：

P4822 [BJWC2012] 冻结

P1266 速度限制

P4568 飞行路线

P1948 Telephone Lines S

P3119 [USACO15JAN] Grass Cownoisseur G 缩点 + 分层图

利用 Bellman-Ford 或者 SPFA 算法，我们可以在 O(nm) 内判断一张图是否存在负环。具体的，我们令 cnt_x 表示起点 s 到点 x 的最短路径包含的边数，当执行松弛操作时，同时更新 cnt 数组。此时如果 cnt_y \ge n，则说明图中有负环。

差分约束系统指若干个形如 X_i - X_j \le c_k 的不等式组，求一组满足所有约束条件的解。

对于若干二元关系约束，我们可以把这些条件转化为图上问题，最常见即在两者间连边。

把每个变量 X_i 看作有向图中的一个节点，对于约束条件 X_i - X_j \le c_k，从 j 向 i 连一条长为 c_k 的有向边。 注意到原图并不一定连通，我们可以建立超级源点 0, 向每个节点连一条长度为 0 的有向边。若图中存在负环，则该系统无解，否则以 0 为起点计算单源最短路，X_i = dis_i 即为所求的一组解。

全源最短路即图中任意两点间的最短路径，求解全源最短路，我们通常使用 Floyd 算法。

Floyd 的本质是动态规划，设 D_{k,i,j} 表示编号不超过 k 的节点的最短路长度，我们可以得到状态转移方程 D_{k,i,j} = \min(D_{k-1,i,j},~D_{k-1,i,k}+D_{k-1,k,j})，时间复杂度 O(n^3)。

注意这里 k 是阶段，必须置于最外层循环中。

类似背包问题的状态转移方程，我们可以压掉 k 这一维，开始用 D 保存邻接矩阵，然后执行动态规划，状态转移：D_{i,j} = \min(D_{i,j},~D_{i,k}+D_{k,j})。

传递闭包，指通过具有传递性的二元关系，推导出尽量多的元素的关系的问题。

使用 Floyd 算法可以解决传递闭包问题。

考虑 Floyd 算法的过程，当外层循环 k 开始时， D_{i,j} 就是编号不超过 k - 1 的节点从 i 到 j 的最短路。

那么，\min(D_{i,j}+a_{j,k}+a_{k,i}) 就是经过节点 k，且由编号不超过 k 的节点的构成的最小环的长度，其中 a 为读入的邻接矩阵。

我们对于所有的 k 计算后取最小值，即可得到整张图的最小环。

对于有向图的最小环问题，我们可以枚举起点 s，使用 Dijkstra 算法求解单源最短路径，取出 s 并更新完后，我们令 dis_s = +\infty, 当 s 第二次从堆中取出时，dis_s 就是经过 s 的最小环的长度。

Tarjan算法

Tarjan 算法可以在线性时间内快速求解无向图和有向图的连通性问题。