记录下由 min 与 + 运算转换成类似于矩阵乘法的推导过程,有错误请在评论区指出 qwq。
我们先简单证明一下矩阵乘法的结合律。设有矩阵 A_{n \times m},B_{m \times p},C_{p \times q},要证明 (AB)C = A(BC)。等价于证 \left({(AB)C}\right)_{i,j} = \left({A(BC)}\right)_{i,j},其中 {A}_{i,j} 表示矩阵 A 的第 i 行第 j 列的元素。
\begin{align} \left({(AB)C}\right)_{i,j} &= \sum_{u=1}^{p}{(AB)_{i,u}} \times C_{u,j} \\\\ &= \sum_{u=1}^{p} \left( {\sum_{k=1}^{m}{A_{i,k} \times B_{k,u}}} \right) \times C_{u,j} \\\\ &= \sum_{u=1}^{p} \left( {\sum_{k=1}^{m}{A_{i,k} \times B_{k,u} \times C_{u,j}}} \right) \\\\ &= \sum_{k=1}^{m} \left( {\sum_{u=1}^{p}{A_{i,k} \times B_{k,u} \times C_{u,j}}} \right) \\\\ &= \sum_{k=1}^{m}{A_{i,k} \times \left( \sum_{u=1}^{p}{B_{k,u} \times C_{u,j}} \right)} \\\\ &= \sum_{k=1}^{m}{A_{i,k} \times (BC)_{k,j}} \\\\ &= \left({A(BC)}\right)_{i,j} \end{align}
因此根据矩阵乘法的结合律,对于 \overbrace{A \cdots A}^{n} 可以写成 A^n,并假设 n = 2^{b_k} + 2^{b_{k- 1}} + \cdots + 2^{b_0},其中 k = \left\lfloor \log{x} \right\rfloor,\forall i \in [0,k], b_i \in \{ {0,1} \},利用结合律我们就可以通过 O(\log{n}) 的复杂度来计算得到
A^n = A^{2^{b_k} + 2^{b_{k- 1}} + \cdots + 2^{b_0}} = A^{2^{b_k}} \times A^{2^{b_{k-1}}} \times \cdots \times A^{2^{b_0}}
其中上面的证明过程用到的运算包括 + 与 \times 以及对应的交换律、结合律和分配律。对于矩阵乘法
(AB)_{i,j} = \sum_{k=1}^{m}{A_{i,k} \times B_{k,j}}
为了更一般化,我们用运算符 \oplus 和 \otimes 来代替上面的加法与乘法,得到:
(AB)_{i,j} = \bigoplus_{k=1}^{m}{A_{i,k} \times B_{k,j}}
其中 \oplus 和 \otimes 满足交换律:
\begin{array}{center} a \oplus b = b \oplus a \\\\ a \otimes b = b \otimes a \end{array}
结合律:
\begin{array}{center} (a \oplus b) \oplus c = a \oplus (b \oplus c) \\\\ (a \otimes b) \otimes c = a \otimes (b \otimes c) \end{array}
\otimes 对 \oplus 的分配律:
a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)
很明显矩阵乘法中的加法 + 和 \times 就分别对应于 \oplus 和 \otimes。同时发现把 \min 代入 \oplus,+ 代入 \otimes ,也满足上面定义的一般形式,只需验证这三个性质均成立即可。
交换律:
\begin{array}{center} \min \{ a,b \} = \min \{ b,a \} \\\\ a + b = b + a \end{array}
结合律:
\begin{array}{center} \min \left\{ \min\{ a,b \}, c \right\} = \min \left\{ a,\min\{ b,c \} \right\} \\\\ (a+b)+c = a+(b+c) \end{array}
+ 对 \min 的分配律:
a + \min \{ b,c \} = \min \{ a+b, a+c \}
因此有
(AB)_{i,j} = \min_{1 \leq k \leq m} \left\{ A_{i,k} + B_{k,j} \right\}
因此对于由 \min 与 + 所构成的运算是具有结合律的,因此对于 \overbrace{A \cdots A}^{n} 同样可以写成 A^n,并且有
A^n = A^{2^{b_k} + 2^{b_{k- 1}} + \cdots + 2^{b_0}} = A^{2^{b_k}} \times A^{2^{b_{k-1}}} \times \cdots \times A^{2^{b_0}}
注意这里的 A \times B 是指两个矩阵间的运算,不是一般意义的矩阵乘法。对于 \min 和 + 有
(A \times B)_{i,j} = \min_{1\leq k \leq m} \left\{ A_{i,k} + B_{k,j} \right\}
而一般意义的矩阵乘法是
(A \times B)_{i,j} = \sum_{k=1}^{m}{A_{i,j} \times B_{j,k}}
我们通过Floyd求最短路这道题目对这个性质进行运用。
这里我们不用传统 Flody 的 dp 状态定义,而是定义状态 f(k,i,j) 表示从 i 到 j 且经过不超过 k 条边的所有路径所构成的集合中最短的路径长度。
对于任意两点 (v, w) 间的距离,答案就是 f(n-1, v, w),这是因为题目保证没有负环,因此任意两点间的最短路径不会超过 n-1 条边。
根据从 i 到 j 的路径中所经过的点 u 来把路径分成两段,其中前面一段 i \to \cdots \to u 经过不超过 k-1 条边,后面一段 u \to \cdots \to j 经过不超过 1 条边。这样就得到状态转移方程:
f(k,i,j) = \min_{1 \leq u \leq n} \{ f(k-1,i,u) + f(1,u,j) \}
这种做法的时间复杂度为 O(n^4)。这个时候就可以利用上面的性质来进行优化了。
我们把 f(k,i,j) 看成是矩阵 F^{k}_{n \times n} 第 i 行第 j 的元素,因此上面的状态转移方程就变成了
F^{k}_{i,j} = \min_{1 \leq u \leq n}\left\{ F^{k-1}_{i,u} + F^{1}_{u,j} \right\}
矩阵间的运算就是 F^{k} = F^{k-1} \ F^{1},通过递推可以发现有 F^k = \left( F^1 \right)^k,而我们最终要求的矩阵就是 F^{n-1} = \left( F^1 \right)^{n-1}。
这里的 F^k 是一个 n \times n 的矩阵,里面的每一个元素 F^{k}_{i,j} 表示从 i 到 j 经过不超过 k 条边的最短路径。
这里就可以用快速幂来求 F^1 的 n-1 次方来得到 F^{n-1},要注意是由 \min 与 + 所构成的运算规则。
同时根据定义知道矩阵 F^0 中任意一个元素 F^{0}_{i,j} 表示 i 到 j 不经过任何边的最短路径,因此有
F^0 = \begin{bmatrix} 0 & \infty & \cdots & \infty \\\\ \infty & 0 & \cdots & \infty \\\\ \vdots & \vdots & \ddots & \vdots \\\\ \infty & \infty & \cdots & 0 \end{bmatrix}
F^{n-1} = F^0 \ \left( F^1 \right)^{n-1}。
这样时间复杂度就降到了 O(n^3 \log{n}),虽然还是不如传统的 Flody 算法,但这种做法给了我们很多启示,比如魔法和牛站就是利用这种思想实现的。
O(n^3 \log{n}) 做法的 AC 代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n, m, k;
int f[N][N], g[N][N], tmp[N][N];
void mul(int c[][N], int a[][N], int b[][N]) {
memset(tmp, 0x3f, sizeof(tmp));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
// 类似于矩阵乘法的c[i][j] = sum(a[i][k] * b[k][j])
// 对于min和+运算有c[i][j] = min{a[i][k] + b[k][j]}
tmp[i][j] = min(tmp[i][j], a[i][k] + b[k][j]);
}
}
}
memcpy(c, tmp, sizeof(tmp));
}
int main() {
scanf("%d %d %d", &n, &m, &k);
// 一开始g=F^0
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = g[i][j] = INF;
}
f[i][i] = g[i][i] = 0;
}
// 一开始f=F^1
while (m--) {
int v, w, wt;
scanf("%d %d %d", &v, &w, &wt);
f[v][w] = min(f[v][w], wt);
}
m = n - 1; // 快速幂求F^{n-1}
while (m) {
if (m & 1) mul(g, g, f);
mul(f, f, f);
m >>= 1;
}
// 这时有g=F^{n-1}
while (k--) {
int v, w;
scanf("%d %d", &v, &w);
if (g[v][w] > INF >> 1) printf("impossible\n");
else printf("%d\n", g[v][w]);
}
return 0;
}
谢谢佬,没想到代数系统真的是有用的orz