邻接矩阵妙用

大部分来源是OIwiki

说到底邻接矩阵也是矩阵，也是用来描述一个状态转移过程的，这个状态可以是一个点集（向量），也可以是所有点对（矩阵）。

首先是用起点向量乘邻接矩阵转移到终点向量。

快速求从一些起点走 \(k\) 步能到达的点

可以用起点向量乘上邻接矩阵的 \(k\) 次方表达，可以用 bitset 优化。

然后是OIwiki中提到求两点路径问题，用 \(k\) 时答案矩阵乘上邻接矩阵得到 \(k+1\) 时的答案矩阵。
通常 \(k=1\) 时的答案矩阵和邻接矩阵类似，可能是边数或边权。

对于所有点对统计长为 \(k\) 的路径数

答案矩阵是两点边数，转移乘上邻接矩阵的 \(k-1\) 次方。

边有边权，对于所有点对统计长为 \(k\) 的最短路

答案矩阵是两点间边权最小值，转移时 \(Ans_{k+1}[i,j]=\min\limits_{1\le q\le n}\{Ans_k[i,p]+G[p,i]\}\)，发现和矩阵乘法类似，所以我们自定义一个新的矩阵乘即可。

统计长小于等于 \(k\) 的路径

同样适用于统计长小于等于 \(k\) 的路径数和最短路。

我们只需要在原本的算法基础上给每个点添加一个边权为 \(0\)，长为 \(1\) 的自环即可。