最短路

对于 Alex_Wei 老师的图论内容的学习。

最短路

一些套路

P1462

套路题，考虑二分转判定。只用点权 \(\leq mid\) 的边然后跑最短路即可。

P4568

\(k\) 很小，所以直接记录到最短路状态中即可。其实就是分层图最短路。

CF1765I

会发现 \(y\) 很小，所以斜着走势必只能够到达很少的行，所以把行离散化一下 bfs 即可。

代码写起来挺魔怔的。

P5304

好牛的套路。

考虑一种做法，把关键点分成两个集合 \(S, T\)，建超级源点汇点 \(s, t\)，那么 \(S\) 中的点到 \(T\) 中的点的最短路就是 \(s \rightarrow t\) 的最短路。

我们会发现将关键点分为两个集合与二进制中的 \(0, 1\) 不谋而合。所以不妨根据每一位的 \(0, 1\) 跑一次最短路。

由于两个点 \(u \not = v\) 至少有一个二进制位不一样，所以一定能够遍历到所有情况。

ABC232G

取模的题首先考虑根据模 \(M\) 建环，即 \(x_i \rightarrow x_{i + 1 \bmod M}\)，边权为 \(1\)。

然后再对原图上的点 \(i\) 连 \(i \rightarrow x_{-a_i \bmod M}\)，\(x_{b_i \bmod M} \rightarrow i\)，边权为 \(0\)。

这样你会发现原图上一条从 \(i \rightarrow i + 1\) 的边对应了新图上 \(i \rightarrow x_{-a_i \bmod M} \rightarrow x_{-a_i + 1 \bmod M} \rightarrow ... \rightarrow x_{b_{i + 1}} \rightarrow i + 1\)。这样子中途走的贡献是 \(b_{i + 1} + a_i \bmod M\)，正好与原图的边权相等。

但这样建图还是要建 \(O(M)\) 个点，会发现有用的点很少，所以离散化一下就做完了。

还有一个神秘数据结构做法，首先这是一个完全图。将 \(b\) 排序后 \(a_i + b_j \bmod m\) 的贡献分为两种，所以二分求出分界点，前一半和后一半分别用线段树维护。

**P7516

待补

SPFA 判负环

两种方式，一种是判入队次数 \(\geq n\)，一种是判最短路长度 \(\geq n\)，一般来说第二种跑的更快。

差分约束

根据三角形不等式，一个跑完 dijkstra 的图上（假定跑最短路）一定满足 \(d_u \leq d_v + w\)。

所以假如我们转化题目得到了例如 \(x_a - x_b \leq c\) 的限制要求一组 \(x\) 的解，我们就可以建图跑最短路。每个点的最短路长度就是一组解。

小技巧，建超级源点 \(S\) 像每个点连边 \(0\) 防止图不联通。

P4926

阅读题面得到式子 \(x_a \geq (k - T)x_b\) 或 \((k + T)x_a \geq x_b\)。

先二分答案把 \(T\) 变成常数，然后两边取 \(\log\)。原因是差分约束如果有乘法一定没法做，所以根据对数的性质变成加法。

那么有 \(\log{x_a} \geq \log (k - T) + \log x_b\) 或是 \(\log (k + T) + \log x_a \geq \log x_b\)。

对于第一种情况建边 \((a, b, -\log (k - T))\)，第二种情况建边 \((a, b, \log(k + T))\)。

然后对于 \(x_c = v\) 新建一个点 \(S\) 与所有的 \(c\) 分别连 \(v\) 和 \(-v\) 的边即可。

这里会有一个疑问，我们只能保证 \(x_s + \log v \leq x_c \leq x_s + \log v\) 即 \(x_s + \log v = x_c\)，是如何使得 \(x_c = v\) 的呢？

刚开始想觉得 \(x_s = 0\)，但我们这样连边只能保证 \(x_s \leq 0\)。其实是因为我们保证了 \(x_c - x_s = \log v\)，所以如果 \(x_s\) 进行了平移那么为了满足等式所有被限制的 \(x_c\) 也会跟着平移。也就是说我们只需要使得相对差确定就可以差分约束判定了，不需要严格相等。

你要做的不是求出每个结点的绝对 \(x_i\) 而是检测差分约束是否矛盾（存在负环）！

还有一点是这样为什么不会影响负环判定，原因是负环只与边权有关，与 \(x\) 无关。

P5590

由于边权 \(\in [1, 9]\)，我们可以得到 \(1\leq d_v - d_u \leq 9\)，所以连边 \((v, u, -1), (u, v, 9)\) 即可。

注意我们只能限制处于 \(1 \sim n\) 最短路上的边。

P3530

是比较难的一个差分约束了。

差分约束模型是好建的，略过不谈，会发现最多 \(x_i\) 种数这个东西很难讨论。你会发现对于第一种连边方式会建两条边互相连接，所以图中两个 SCC 之间的连边一定是第二种连边方式连的边。第二种连边方式的限制很弱，可以任意调整两个相邻 SCC 中的 \(x_i\)。

于是考虑每个 SCC 内部的情况，由于差分约束的模型，对于任意点对 \((u, v)\) 有 \(x_v \leq x_u + d(u, v)\)。其中 \(d(u, v)\) 为 \((u, v)\) 的最小距离。

我们会发现正权边只有 \(1\) 一种情况，所以 \((u, v)\) 的最短路上一定取遍 \(d_{u, v} + 1\) 个值。所以我们只要求出一个 SCC 中的最长最短路即可。

注意到 \(n \leq 600\)，直接对每个 SCC 内 floyd 即可。

P7515

方程数不够不能高斯消元，会多出 \(n + m - 1\) 个自由元。

考虑将自由元分布在矩阵的最右列和最下行，这样可以很简单地通过 \(b\) 还原出 \(a\)。但这样还原出的 \(a\) 不一定满足 \([0, 1000000]\) 的限制。

会发现如果对一行进行 \(+-+-...\) 的操作后依然合法，列同理。所以不妨对于每一行每一列交替进行 \(+-\)，这么做会有某些地方符号相同，所以对于偶数行和列 \(-+-+\) 即可。于是设修改了 \(x_{i, j}\)，则我们需要满足 \(0 \leq a_{i, j} + x_{i, j} \leq 1000000\)，变成了差分约束的式子。

差分约束极值解

一般来说差分约束维护了变量之间的差值关系所以很难得到极值。

但我们令 \(x_i \leq 0\)，我们将它看作 \(x_0 + 0 \geq x_i\)，其中 \(x_0 = 0\)。那么建立虚点 \(0\) 连边，权值为 \(0\)。则此时我们可以断定 SPFA 求得的解必然为字典序最大解。

原因是根据三角形不等式，最短路 \(P\) 上的点 \(x_0, x_1, ..., x_u\) 满足，\(x_i - x_{i - 1} = l_i\)。假设将 \(0 \sim u\) 的限制加起来就得到 \(x_u - x_0 = \sum l\)，所以 \(x_u\) 取到了极值。于是每个点到取到了极值，字典序一定最大。

对于最小解，我们令 \(x_i \geq 0\) 就行了。

AGC056C

考虑 \(0/1\) 的经典转化，令 \(0\) 为 \(-1\)，\(1\) 为 \(1\)，则题目约束为 \(S_r - S_{l - 1} = 0\)。同时注意到还有限制 \(|S_i - S_{i - 1}| = 1\)。第一个好处理，第二个由于存在绝对值等式所以很难直接转化成差分约束模型。我们不妨放宽一点约束 \(|S_i - S_{i - 1}| \le 1\)，这是好做的。

根据上文描述，这里直接直接 01 BFS 就可以得到极值。

然后证明一下为什么差分约束最好一定不会跑出来 \(S_i = S_{i - 1}\) 的情况。

根据题目描述我们可以得到 \(0\) 边连接的两个点奇偶性一定相同，而 \(1\) 边连接的两个点奇偶性一定不同，所以出现 \(S_i = S_{i - 1}\) 的情况一定可以将 \(S_i \rightarrow S_{i - 1} + 1\)，会更优。

传递闭包

就是 \(0, 1\) 矩阵上的 floyd，可以通过 bitset 优化。

最短路树

对于点 \(v\) 一定存在 \(d_v = d_u + w\)，记 \(f_v = u\)，从所有的 \(f_i \rightarrow i\) 连单向边，组成一棵叶向树，称为最短路树。可以发现最短路树上每两个点之间的路径都是最短路。

P6880

显然要对 \(1 \sim n\) 和 \(n \sim 1\) 分开考虑，并且二者类似。

对于 \(1 \sim n\) 来说，暴力枚举边翻转时间复杂度过高不做考虑。

考虑建出最短路树，那么不在树上的边无论是否翻转都不影响最短路树上的边，所以可以直接比较一下翻转后的 \(d_v + w + d_u + D\)。

对于最短路树上的边考虑将边翻转后直接跑 dijkstra，由于图为稠密图所以使用 \(\Theta(n^2)\) 的 dijkstra。并且我们枚举的边也是 \(\Theta(n)\) 级别的，总复杂度 \(\Theta(n^3)\) 可以通过。

最短路计数/最短路树计数

最短路计数考虑建出一张最短路 DAG，即将所有 \(d_v = d_u + w\) 的结构加入图中。然后就变成了 DAG 计数问题。

最短路树计数考虑最短路 DAG 的任意一棵生成树均为最短路树，所以用矩阵树定理解决即可。

删边最短路

给定一个无向正权图，对图上每条边求删去该边后 \(1 \sim n\) 的最短路

先设一条最短路为 \(P\)，当前考虑边 \(E(i, j)\)。

如果 \(E \not \in P\)，那么删边后显然没影响。

如果 \(E \in P\)，那么我们采用的做法是枚举每一条边 \((u, v)\)，并且 \(d(1, u)\) 和 \(d(v, n)\) 上均不包括边 \(E\)，然后用 \(d(1, u) + w(u, v) + d(v, n)\) 来更新最短路。

证明太困难了就不证了。

这样做还是比较慢，考虑分别建以 \(1, n\) 为根的最短路树，则对于 \((u, v)\)，令 \(u' = lca(n, u), v' = lca(1, v)\)。

对于 \((u', v')\) 上的所有边都可以用 \((u, v)\) 更新，使用线段树维护一下即可。

P1186

模板题。

写的时候不用把树建出来，考虑使用并查集维护一下每个点最近的在最短路上的点就行了。

P2685

差不多，注意如果删边后最短路长度不变则第二问答案为 \(m\)。

*P3573

其实和删边最短路没什么关系，但思路是类似的。

考虑一条边 \((u, v)\)，由于图是个 DAG 所以我们可以很方便地求出 \(d(1, u)\) 和 \(d(v, n)\)，最长路是好算的。

然后考虑怎么做这个删点的过程，会发现对于边 \((u, v)\) 如果走了它那么拓扑序中与 \(u, v\) 相同的都不能走。用线段树维护一下即可。

代码没写。

*CF1163F

感觉过去还是套路的做法。考虑分情况讨论，如果被修改的 \(E\) 在最短路上那么如果变短了一定还是这条最短路，否则与删边最短路类似线段树维护一下。如果被修改的 \(E\) 不在最短路上那么变长了一定没影响，否则考虑将 \(d(1, u) + w + d(v, n)\) 和最短路长度比较一下即可。

或者直接视作把边删掉和强制经过这条边的最短路的较小值。

代码没写。

平面图最小割

平面图：能画在平面上，满足除顶点外无边相交的图。

网格图：就是一个网格。每个点有自己的编号 \((i, j)\)。

接下来为了好画图以网格图最小割为例（常见的也只有网格图最小割的题）。前提是边权非负并且割的源点和汇点都在网格图的边界上，即 \(i = 1/n\) 或 \(j = 1 / m\)。

考虑求左上角 \(s\) 到右下角 \(t\) 的最小割。

引理：一定存在最小割满足点集 \(S, T\) 分别连通。

原因是如果 \(S\) 不连通一定可以分为包含 \(s\) 的 \(S_1\) 和不包含 \(s\) 的 \(S_2\)，将 \(S_2\) 并入 \(T\)，显然不会使原本不在割集内的边加入割集，反而会让原本在割集内的边离开割集。一定更优。

对网格图建出对偶图，然后从左上角和右下角分别引一条射线将网格图分成两半，右上部分的网格图边界的边对应的对偶图边全部连向超级汇点 \(T'\)，左下角全部连向超级源点 \(S'\)。

如图，黄色的点为 \(S\)，红色的点为 \(T\)，浅蓝色的边为割集，深蓝色的边为割集在对偶图上的对应边，容易发现最小割其实就是 \(T\) 到 \(S\) 的最短路。

于是我们得到平面图最小割等于对偶图最短路。事实上 \(s, t\) 只要在边界上就可以通过对偶图最短路得到平面图最小割。

P4001

模板题。注意数组大小。

*P7916

好神的题目。

考虑建出对偶图，这里将每个无界面也视为一个点。然后只保留黑白交界的点集 \(V\)，会发现 \(|V|\) 要不然是偶数要不然是 \(1\)，是 \(1\) 的情况显然答案就是 \(0\)。

然后考虑还是要在最短路上找做法，显然可以两两匹配，贡献是最短路。如果两组点的最短路有交集那么互相换一下端点一定更优。

所以考虑 DP 设 \(f_{i, j}\) 表示从 \(i \sim j\) 都匹配的最小代价，转移 \(f_{i, j} = \min\{g_{i, k} + f_{i + 1, k - 1} + f_{k + 1, j}\}\)。

详细证明太复杂了不写了我目前也看不懂。

代码还没写。

**K 短路

太难了还没学。

同余最短路

给定 \(n\) 个正整数 \(a_i\)，求有多少个 \(y \in [L, R]\) 能表示为 \(\sum_{i = 1}^n a_ix_i\)，其中 \(x_i \geq 0\)。

一个显然的事情是如果 \(r\) 能被表示那么 \(r + ka_i\) 都能被表示（前提得在范围内）。所以我们不妨取 \(a_1\) 为参考值，设 \(f_i\) 为模 \(a_1\) 余 \(i\) 的同余类中最小能被表示出来的数。则若 \(r \geq f_{r \bmod a_1}\)，\(r\) 就可以被表示。

考虑如何求出 \(f\)。显然 \(f_0 = 0\)，然后有 \(f_j + a_i \rightarrow f_{j + a_i \bmod a_1}\)，相当于一个最短路的过程，用 dij 跑一下即可。

计算贡献时差分一下，对于 \(y \in [0, R]\) 的贡献为 \(\sum_{i = 1}^n \lfloor \frac{R - f_i}{a_1} \rfloor + 1\)。

P2371