最短路（图论学习总结部分内容）

文章目录

- 前言
- 二、最短路
- - 多源最短路
  - 单源最短路
  - - 知识点
    - 例题及变形
    - 欧拉回路
    - 差分约束系统
    - - $e g 1 :$ [P3275 SCOI2011 糖果 - 洛谷](https://www.luogu.com.cn/problem/P3275)（差分约束）
    - $0/1$ 分数规划
    - - [A-Sightseeing Cows(nowcoder.com)](https://ac.nowcoder.com/acm/contest/1059/A)（spfa判负环+二分求解01分数规划问题）
    - 练习题

前言

由于图论学习总结内容过多，全放在一篇博客过于冗长现进行拆分，本文是最短路部分，其他部分地址见：图论学习总结(For XCPC)

二、最短路

多源最短路

$Fl oy d$ 算法

令 $D [i, j]$ 表示**“经过若干个编号不超过k的结点”** 从 $i$ 到 $j$ 的最短路。该问题可以划分为两个子问题，经过编号不超过 $k - 1$ 的结点从 $i$ 到 $j$ ，或者先从 $i$ 到 $k$ ，再从 $k$ 到 $j$ 。于是：
$D [k, i, j] = min (D [k - 1, i, j], D [k - 1, i, k] + D [k - 1, k, j])$
初值为 $D [0, i, j] = G [i, j]$ ，可以看到 $Fl oy d$ 的本质是动态规划， $k$ 是阶段。其中 $k$ 这一维可以省略，即 $D [i, j] = min (D [i, j], D [i, k], D [k, j])$ 。

例题及变形

$eg1：Sorting\ It\ All\ Out$ $(蓝书例题，传递闭包)$

题目大意：

Sorting It All Out

这是一道传递闭包问题，是Floyd算法的简单应用。我们可以对每个形如 $i < j$ 的不等式，令 $d [i, j] = 1$ ，除了 $i < j$ 的其他情况都令 $d [i, j] = 0$ 。我们可以用Floyd算法对 $d$ 求传递闭包，若存在 $d [i, j] = d [j, i] = 1$ 则说明有矛盾，若均为0则说明不能确定关系。此时，我们可以再用二分法，二分 $t$ 的值，判断仅用前 $t$ 个不等式能否判断所有关系。

$eg2:Sightseeing\ trip$ $(蓝书例题， Fl oy d 求最小环)$

题目大意：

Sightseeing strip

我们考虑 $Fl oy d$ 的算法过程。当外层循环 $k$ 刚开始时， $d [i, j]$ 保存着经过编号不超过 $k - 1$ 的结点从 $i$ 到 $j$ 的最短路长度。于是， $\min_{1\leq i<j<k}{\{d[i,j]+g[j,k]+g[k,i]\}}$ 就是满足以下两个条件的最小环长度：1、由编号不超过 $k$ 的结点构成。2、经过结点 $k$ 。前面式子中的 $i, j$ 相当于枚举了环上与 $k$ 相邻的两个点，对 $A \in [1, n]$ 都进行计算，取最小值即是答案(我们在考虑每个 $k$ 只考虑了由编号不超过 $k$ 的结点构成的最小环，由对称性可知，这样不会影响答案)。

$eg3:Cow\ Relays$ $(蓝书例题，倍增优化DP\ or\ 广义矩阵乘法+快速幂优化)$

题目大意：

Cow Relays

$Fl oy d$ 算法是一种以”途径点集大小”为阶段的动态规划算法，在这道题我们可以考虑用以边的数量为阶段的 $D P$ 方法经过倍增优化求解。首先，对于点的编号我们需要先进行离散化，假设离散化后点的数量为 $P$ ， $G$ 为 $P * P$ 的邻接表。我们考虑从 $s$ 出发分别经过 $2^0,2^1,...,2^N$ 条边到 $e$ 的最短路，倍增优化的前提是状态可以按阶段任意划分，所以我们不妨令 $F [i, x, y]$ 表示从 $x$ 出发恰好经过 $2^i$ 条边到达 $y$ 。那么状态转移时的决策，我们只需要枚举中转点 $k$ ，状态转移方程： $\min_{1\le k\le tot} \{F[i,x,y], F[i-1,x,k]+F[i-1,k,y] \}$ 。

我们进一步考虑，其实这道题是一种广义的矩阵乘法，可以通过矩阵快速幂优化。我们考虑以下式子 $\forall i,j\in[1,P]\ \ B[i,j]=\min_{1\le k\le P}\{G[i,k]+G[k,j] \}$ ，在式子中我们枚举了所有的中专点 $k$ ，对于每一对 $(i, j)$ 来说， $B$ 记录的是恰好经过两条边的最短路。

若 $G^m$ 记录了所有点两两之间恰好经过 $m$ 条边的最短路，我们可以初始化 $ans=G^0$ ， $an s [i] [j]$ 表示恰好经过了 $0$ 条边从 $i$ ，到 $j$ 的最短路。那么： $\forall i,j \in[1,P],\ D^{r+m} = \min_{1\le k\le P}\{(D^r)[i,k]+(D^m)[k,j] \}$ ，这个式子其实等价于一个关于 $\min$ 和 $+$ 的广义的"矩阵乘法"，我们可以先用快速幂计算出 $ans^N$ ，最后 $ans^N)[S,E]$ 就是答案，每次矩阵乘法是 $O(T^3)$ ，一共 $\log N$ 次，时间复杂度为 $O(T^3\log N)$ 。

ac代码参考：代码查看 (nowcoder.com)

练习题

Gym-104023-Problem - F (2022 $CCPC$ 威海F，金牌题，Floyd +建图+用类似 $P r im$ 的做法，找出以每个点 s 为根的有向瓶颈生成树)

单源最短路

知识点

$D ijk s t r a$
$SPF A$ 和 $B e ll man - F or d$ （ $SPF A$ 已死）
$01 BFS$ （只适用于边权只有0和1的图）
$拓扑排序 + D P$ (有向无环图)

例题及变形

$e g 1 : 最优贸易$ (B-最优贸易_ )

题目大意：

最优贸易

本题是让我们在一张结点带有权值的图上找出一条从 $1$ 到 $n$ 的路径，使得路径上能够找出两个点 $p, q$ ， $val_p-val_q$ 最大。

我们可以把这张图当作有向图处理，从结点 $1$ 出发跑一次 “最短路” 算法，预处理出当前结点 $x$ 的前驱结点中所有点权的最小权值，记为 $p re [x]$ ，同理我们可以反向建图从 $n$ 出发预处理出在正图中当前结点 $x$ 之后所有点权的最大值记为 $p a s t [x]$ ，最后枚举每个结点 $x$ ，用 $p a s t [x] - p re [x]$ 更新答案即可。

注意，上述预处理中的 “最短路” 算法可以将松弛操作分别改为 $\min和\max$ 那么松弛更新的操作就不满足 $D ijk s t r a$ 的贪心性质，我们可以用 $SPF A$ 算法。

$eg2:Road\ and\ Planes$ (C-Roads and Planes_0x61 图论-最短路)

题目大意：

Road and Planes

这道题是一个十分明显的单源点最短路问题，但图中带有负权边，我们不能直接使用 $D ijk s t r a$ ，又因为有特殊构造的数据，所以我们使用 $SPF A$ 会 $T L E$ 。这时候我们就要注意到**双向边都是非负的，只有单向边可能是负的，并且单向边不构成环。**我们可以利用这一性质解决本题。

如果我们只看双向边，会发现是一个个的连通块，连通块内所有边均为非负边权。那么我们可以对每一个连通块内跑 $D ijk s t r a$ 算法。这时候如果我们把每一个连通块看作一个点的话，那么加上单向边(航线)，那么整个图就是一张有向无环图，不管边权正负，我们都可以通过 $拓扑排序 + 松弛操作$ 在线性时间内求出最短路。

至此，这道题的解法已经很明显了， $拓扑排序套 D ijk s t r a$ 。我们在外层维护每一个连通块的度数 $d e g$ ，在每个块内跑 $D ijk s t r a$ ，遇到负权单向边，则更新连通块的度数用于外层的拓扑排序。

整个的时间复杂度为 $O(T+P+R\log T)$ 具体实现：代码查看 (nowcoder.com)

$eg3:There\ and\ Back\ Again$ $2024 I CPC$ 亚太锦标赛 J

题目大意

There and Back Again

这是一道最短路的变形，题目要求从 $1$ 到 $n$ 再到 $1$ 的最短距离，并且要求 $1$ 到 $n$ 和 $n$ 到 $1$ 的路径不相同。

首先，我们考虑最短路，要想总和最小那么去和回至少有一条是最短路，不妨就去时走最短路，那么 $1$ 到 $n$ ，我们可以直接在图中跑 $D ijk s t r a$ 算法记为 $d 1$ ，考虑回的时候，我们可以再以 $n$ 为起始点跑一边最短路，记为 $d 2$ ，我们可以枚举每一条边，如果不在去的路径中，我们用 $d 1 [x] + d 2 [y] + w$ 更新答案，其最小值就是我们需要的答案。

实现细节：C++可以用链式前向星存图，边的话就有对应下标，开个数组标记即可，python的话用邻接表存图，直接用set当vis即可，ac代码参考( $P y t h o n$ )：Submission #256743872 - Codeforces

$e g 5 :$ $[NO I P 2017]$ P3953 NOIP2017 提高组] 逛公园 - 洛谷 | 计算机科学教育新生态

题目大意

策策同学特别喜欢逛公园。公园可以看成一张 $N$ 个点 $M$ 条边构成的有向图，且没有自环和重边。其中 $1$ 号点是公园的入口， $N$ 号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。

策策每天都会去逛公园，他总是从 $1$ 号点进去，从 $N$ 号点出来。

策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果 $1$ 号点到 $N$ 号点的最短路长为 $d$ ，那么策策只会喜欢长度不超过 $d + K$ 的路线。

策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？

为避免输出过大，答案对 $P$ 取模。如果有无穷多条合法的路线，请输出 $- 1$ 。

输入格式

第一行包含一个整数 $T$ , 代表数据组数。

接下来 $T$ 组数据，对于每组数据：第一行包含四个整数 $N, M, K, P$ ，每两个整数之间用一个空格隔开。

接下来 $M$ 行，每行三个整数 $a_i,b_i,c_i$ ，代表编号为 $a_i,b_i$ 的点之间有一条权值为 $c_i$ 的有向边，每两个整数之间用一个空格隔开。

输出格式

输出文件包含 $T$ 行，每行一个整数代表答案。

【测试数据与约定】

对于不同的测试点，我们约定各种参数的规模不会超过如下

测试点编号	$T$	$N$	$M$	$K$	是否有 $0$ 边
$1$	$5$	$5$	$10$	$0$	否
$2$	$5$	$10^3$	$2\times 10^3$	$0$	否
$3$	$5$	$10^3$	$2\times 10^3$	$50$	否
$4$	$5$	$10^3$	$2\times 10^3$	$50$	否
$5$	$5$	$10^3$	$2\times 10^3$	$50$	否
$6$	$5$	$10^3$	$2\times 10^3$	$50$	是
$7$	$5$	$10^5$	$2\times 10^5$	$0$	否
$8$	$3$	$10^5$	$2\times 10^5$	$50$	否
$9$	$3$	$10^5$	$2\times 10^5$	$50$	是
$10$	$3$	$10^5$	$2\times 10^5$	$50$	是

对于 $100\%$ 的数据， $\le P \le 10^9$ ， $\le a_i,b_i \le N$ ， $\le c_i \le 1000$ 。

数据保证：至少存在一条合法的路线。

2019.8.30 增加了一组 hack 数据 by @skicean
2022.7.21 增加了一组 hack 数据 by @djwj233

题目分析

关于方案数的统计，我们考虑动态规划，令 $F [y] [k]$ 表示从起点到 $y$ ，比最短路多 $k$ 的长度的路径方案数。状态转移： $\sum_{dist[x]+t+w(x,y)=dist[y]+k} F[x][t]$ 。对于这样的转移，我们需要按照一定的顺序，我们发现我们的阶段是 $k$ , 即我们要先算 $F [1... n] [0]$ 再算 $F [1... n] [1]$ ，以此类推。

我们不妨直接写成记忆化搜索，这样我们就可以忽略顺序的问题了。记忆化搜索的入口是直接从第 $n$ 个点开始往前回溯，在返回时更新状态，我们需要一张与原图完全相反的图。

关于无穷多合法路线的理解：图中含有 $0$ 环，且和答案有关的路径有关系，这个需要单独判断。如果有 $0$ 环，我们在记忆化搜索时会重复访问到 $F [y] [k]$ ，我们在记忆化搜索中加一个访问标记即可。

启发

关于最短路有要求多少条边的(如牛站)，有路径条数计数或方案计数的(如习题 $RO A D$ )，或是要将 $d i s t$ 限制在某一区间里的(如上一道例题 $P er m u t a t i o n$ $P u zz l e$ )一般都用到了动态规划递推求解，区别在于阶段和状态的表示与转移不同。可见对于类似的这类问题，我们一般会通过分解为子问题的方式通过动规来求解，在比赛中遇到此类问题需要有一定的灵敏性。

欧拉回路

差分约束系统

差分约束系统是一中特殊的 $N$ 元一次不等式组。它包含 $N$ 个变量 $X_1$ ~ $X_N$ 以及 $M$ 个约束条件，每个约束条件都形如 $X_i-X_j\le c_k$ 其中 $c_k$ 是常数。我们的问题就是求一组解 $X_1,X_2,...,X_N$ 是所有的约束条件满足，或确定其无解。

$e g 1 :$ P3275 SCOI2011 糖果 - 洛谷（差分约束）

题目大意

幼儿园里有 $N$ 个小朋友， $\text{lxhgww}$ 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， $\text{lxhgww}$ 需要满足小朋友们的 $K$ 个要求。幼儿园的糖果总是有限的， $\text{lxhgww}$ 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。