[洛谷 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;
}

《[洛谷 6190][NOI Online 2020 入门组]魔法》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据