矩阵乘法解决图上问题

GGapa · 2024-06-13 16:40:32 · 算法·理论

解决的问题

博客

洛谷专栏

矩阵乘法在图论中常用于(定长/限制类)路径统计和最短路问题。此类型题目的时间复杂度往往是 O(n^3 \log k)，故此类题目的点数不应过大。

• OI-wiki

一些代码技巧

struct Mat {
    int n; 
    vector<VI> A;
    vector<int>& operator [](int i)  {return A[i];} 
    const vector<int>& operator [](int i) const { return A[i]; } //在矩阵乘法中放入这两个函数之后，便可以直接通过 `ans[1][5]` 访问数组元素，而不是 `ans.a[1][5]`。
    Mat(int _n) : n(_n) {A.assign(n + 1, VI(n + 1, 0)); }
    const Mat operator*(const Mat &B) const {
        Mat C(n);
        rep(i, 0, n) rep(j, 0, n) 
            rep(k, 0, n) (C[i][j] += (A[i][k] * B[k][j]) % mod) %= mod;
        return C;
    }
};

题

P2233 [HNOI2002] 公交车路线

定长

模板题，按照题意在每个公交站之间连边即可，注意的是在到达终点之后不能从终点出来，终点的出度是 0。

P4159 [SCOI2009] 迷路

定长

看到题目和数据范围后，不难想到矩阵快速幂求解 k 步内到达某一结点的方案数这一类问题。

但是问题出现了，因为上述做法只能满足 "01矩阵"。

那我们就考虑将这个矩阵转化为 01矩阵不就完事了吗？

考虑给每个节点建立 8 个虚点，我们令 (i,j) 表示距离节点 i，j 个距离的点，(i,0) 就代表节点 i，我们需要将 (i, j) 和 (i, j-1 ) 通过一条有向边连接起来。

若此时有边连向这个节点，且距离为 d，那么我们就将它连接到 (i, d - 1) 的节点处就可以了，此时这个邻接矩阵就转化为了 01 矩阵。

时间复杂度：O((9n)^3 \log T)

总结：如果一道题目是某类题型的变种，那我们可以将这道题想办法转化为我们熟悉的题型；

trick: 若路径长度 \ge 1 可以建虚点，虚点之间的路径长度是 1，总长度依然等于原长。

P3758 [TJOI2017] 可乐

限长

这道问题引入了停留和爆炸两个特殊的情况：

• 爆炸意味着不能再往后更新状态，故可以建立一个汇点，进了汇点就不能再出来，就满足了不能再往后更新状态
• 停留意味着花费一单位时间不动，建立自环就好，建立自环还可用于解决限长类问题。

以上两点也是矩阵乘法解决路径类问题常用的 trick。

P2886 [USACO07NOV] Cow Relays G

定长最短路

定长最短路板子题，但是有一点值得一提，很容易搞混。关于 \texttt{ans} 数组的初值问题。

在路径统计中 \texttt{ans}[i][j] 的定义是从 i - j 有多少种方案，很显然 \texttt{ans}[i][i] = 0，但是在最短路中，\texttt{ans}[i][j] 的定义是从 i-j 的最短路是多少，所以 \texttt{ans}[i][i] = 0，而其他的应当等于 \infty。

P6569 [NOI Online #3 提高组] 魔法值

定长

首先看题目数据范围，n \leq 100 ，这种情况要么说明这道题的时间复杂度是比较高的，要么就和矩阵乘法脱不开关系。

阅读题目之后，我们发现可以应用 Floyd 最短路，也就是矩阵乘法的思想去描述每一轮每一个城市的魔法值。

故这道题应该先用邻接矩阵建图，矩阵快速幂求解。

结果就超时了，考虑通过倍增，二进制分解优化。

预处理时间复杂度 O(n^3\log n) ，单次询问时间复杂度 O(n^2\log n) 。

总结：对于数据范围比较小的图论题要联想到邻接矩阵，对于经常会用到的数据不必重复计算，考虑记录下来优化程序的运行效率。

倍增适合于各种各样的优化，非常实用 快速幂也算是二进制拆分，二进制拆分可以用于快速幂的预处理，还能用于喝果汁那道题 像这种和步数有关的题，应该联想到邻接矩阵，邻接矩阵虽然不常用，但是依然很重要。

trick: 若需要执行多次快速幂，考虑提前预处理 base。

P5188 [COCI2009-2010#4] PALACINKE

限长类问题。

朴素的 DP 很好想，不再赘述且貌似对思考正解没有帮助。