[洛谷 6190][NOI Online 2020 入门组]魔法

题目链接

https://www.luogu.com.cn/problem/P6190

题解

作为一名参加了提高组却爆炸的菜鸡，在入门组进行的时候口胡了一下这题的解法。

我们来根据 \(k\) 的情况分类讨论下：

• \(k=0\)

非常 trivial 的情况，直接跑 Floyd 即可得出结果。

• \(k=1\)

考虑从 \(k=0\) 的情况推 \(k=1\) 的情况。

设 \(f_{k,i,j}\) 表示在使用不超过 \(k\) 次魔法的情况下，从 \(i\) 到 \(j\) 的最短路。

现在我们知道了 \(f_{0,i,j}\)，如何得到 \(f_{1,i,j}\) 呢？

边的规模只有 \(2500\)，我们可以直接枚举要用魔法的边，转移时强制走这条边，求最短路。

假如边 \((u,v,w)\) 用了魔法，转移方程如下：

$$
f_{1,i,j}=\min\{f_{0,i,j},\min f_{0,i,u}+f_{0,v,j}-w\}
$$

• \(k=2\)

我们已经得到了 \(k=1\) 的情况，如何推 \(k=2\) 的情况呢？

类似于 Floyd，我们可以枚举一个中转点 \(k\)，\(i \to k\) 最多用一次魔法，\(k \to j\) 最多用一次魔法，合并起来就是最多两次魔法的答案了。

写成式子长这样：

$$
f_{2,i,j}=\min f_{1,i,k}+f_{1,k,j}
$$

如果你做过很多矩阵优化的题，会发现这个形式挺像矩阵乘法。

所不同的是：原来是若干个乘积的和相加，现在变成了若干个和取最小值。

类比一下，我们猜想这个可以用矩阵快速幂来优化转移。

• \(k \gt 2\)

根据 \(k=2\) 的情况，我们猜想：最多用 \(i\) 次魔法的结果和最多用 \(j\) 次魔法的结果按照上面的转移方式合并的话，可以得到最多用 \(i+j\) 次魔法的结果。

这个成立的前提是我们定义的这个矩阵运算要具有结合律，这样我们才能用快速幂来计算。

数的加法和乘法都满足结合律，从而有龟速乘和快速幂。

矩阵的乘法满足结合律，从而能用矩阵快速幂加快计算速度。

我们这个运算满足结合律吗？答案是肯定的。

这个可以感性理解下，严谨的证明留给各位读者练习。

到这里本题就得到了完美解决。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct edge
{
 int u,v,w;
}e[2505];
int n,m,k;
struct mat
{
 long long a[105][105];
 mat(int x=63)
 {
  memset(a,x,sizeof(a));
 }
 mat operator*(const mat&b)const
 {
  mat ans;
  for(int k=1;k<=n;k++)
   for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
     ans.a[i][j]=min(ans.a[i][j],a[i][k]+b.a[k][j]);
  return ans;
 }
}a;
long long f[105][105];
mat fpow(mat x,int y)
{
 mat ans;
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
   ans.a[i][j]=f[i][j];
 while(y)
 {
  if(y&1)ans=ans*x;
  x=x*x;
  y>>=1;
 }
 return ans;
}
int main()
{
 memset(f,63,sizeof(f));
 cin>>n>>m>>k;
 for(int i=1;i<=n;i++)
  f[i][i]=0;
 for(int i=1;i<=m;i++)
 {
  cin>>e[i].u>>e[i].v>>e[i].w;
  f[e[i].u][e[i].v]=e[i].w;
 }
 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]);
 for(int k=1;k<=m;k++)
 {
  int u=e[k].u,v=e[k].v,w=e[k].w;
  for(int i=1;i<=n;i++)
   for(int j=1;j<=n;j++)
    a.a[i][j]=min(a.a[i][j],min(f[i][j],f[i][u]+f[v][j]-w));
 }
 if(k==0)cout<<f[1][n]<<endl;
 else cout<<fpow(a,k).a[1][n]<<endl;
 return 0;
}