自动搬运

查看原文

来自洛谷，原作者为

	guodong **

搬运于2025-08-24 21:43:02，当前版本为作者最后更新于2019-07-27 14:44:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

浅谈矩阵加速优化动态规划

本文只适用于OI学习

矩阵乘法

给定两个矩阵

$A=\begin{bmatrix}1 &2 &3 \\ 4& 0&1\end{bmatrix}$

$B=\begin{bmatrix}1 &2 \\ 2 &0 \\ 3 &1\end{bmatrix}$

那么,$A \times B=C$

$C=\begin{bmatrix}1\times1+2\times2+3\times3 & 1\times 2 +2\times0+3\times1 \\ 4\times1+0\times 2 + 1\times3 & 4\times2+0\times 0 +1\times 1\end{bmatrix}$

用数学公式表述那就是： $C_{ij}=\sum_{k=1}^{n}A[i][k]*B[k][j]$

一般来说，$A$的行数$B$的列数，$B$的行数也等于$A$的列数，当两个不满足上述条件的矩阵相乘时，我们可以通过补零的方式使他们满足。

由于矩阵乘法满足分配率，结合律（但是不满足交换律！）,所以我们可以通过矩阵快速幂的方法来加速

$tips:$矩阵加速利用的是矩阵乘法满足结合律

---

Floyd

$Floyd$是一种最短路算法，适用于点数较少的图

$Floyd$的本质是动态规划,它的状态定义以及转移：

设$f[i][j]$为$i$到$j$的最短距离

$f[i][j]=min(f[i][j],f[i][k]+f[k][j])$

代码实现：

	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

我们魔改一下：

	int C[N][N];
	memset(C,127,sizeof C); // inf
	for(int k=1;k<=n;j++)
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				C[i][j]=min(C[i][j],A[i][k]+A[k][j]);
	}
	memcpy(A,C,sizeof C);	

$Q$:这两种写法等价吗？

$A$:当然不是，floyd是动态规划f[i][k]+f[k][j]是已知的最优状态的转移，但是第二种却是两个初始矩阵简单的相乘。

$tips:$这里的矩阵乘法由原来的$C[i][j]=A[i][k]+B[k][i]$,变成了$C[i][j]=\color{red} {min(C[i][j],A[i][k]+A[k][j])}$ 之所以可以加$\color{red} min$，是因为$min$也满足结合律:$min(min(a,b),c)=min(a,b,c)=min(a,min(b,c))$

那么它代表的意义又是什么呢？ 先放出例题

让我们做下列这个实验： 实验代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int A[1001][1001];
int C[1001][1001];
signed main()
{
	freopen("data.in","r",stdin);
	int n,m;
	scanf("%d %d",&n,&m);
	memset(A,50,sizeof A);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d %d %d", &a,&b,&c);
		A[a][b]=A[b][a]=c;
		A[i][i]=0;
	}
	int tmp=1;// 看这里！！！！！！！！
	while(tmp--)
	{
		memset(C,127 , sizeof C);

		for(int k=1;k<=n;k++)
		{
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					C[i][j]=min(C[i][j],A[i][k]+A[k][j]);
		}
		memcpy(A,C,sizeof C);	
	}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
				if(A[i][j]<100)
					printf("%d ",A[i][j]);
				else
				{
					printf("X ");
				}
			printf("\n");
		}
}

给出一条链：

$1-2-3->4-5\dots-10$

输入的邻接矩阵$A$，可以理解成经过一条边的最短路，我们记做$A^{1}$.

$C=A\times A, C= A^{2}$，然后把$A$赋值成为$C$，也就是$A^{2}$

容易发现，当$tmp=x$时，$C$为$A^{2^{x}}$

下面是我记录的实验数据:

tmp	邻接矩阵第一行（也就是点1到各个点距离）$X$为不连通
1	0 1 2 X X X X X X X
2	0 1 2 3 4 X X X X X
3	0 1 2 3 4 5 6 7 8 X

---

容易发现，${A^{x}}$是表示$A$经过了$x$条边的最短路。

于是上边的例题就能通过矩阵快速幂轻松解决！