【题解】洛谷 P6190 [NOI Online #1 入门组] 魔法

· · 题解

前言

其实其他题解讲得很清楚了，这篇题解主要是想讲一下如何把矩阵快速幂的初始化的时间复杂度由 O(n^2m) 优化到 O(nm)，同时加深大家对矩阵乘法的理解。

题解

还是先简单说一下题目解法：

首先要最优，显然 k 次魔法要用完。（即使只剩下 1 次魔法，你选一条边走出去又走回来，答案不会更差）

所以我们只需将 k 段恰好使用 1 次魔法的路径拼起来。

由于 k \le 10^6 稍微有点大，但 n \le 100，于是 Floyd 预处理两点间距离，进一步预处理出任意两点之间恰好使用 1 次魔法的最小代价，再上一个 O(n^3 \log{k}) 的广义矩阵快速幂即可解决。

P.S. 所谓的广义矩阵乘法，就是把普通矩阵乘法中求和（\Sigma）换成求最值（\max 或 \min），乘法（\times）换成加法（+）。易证其满足普通矩阵乘法的运算律。

考虑矩阵乘法应用在类似图论问题中的本质，发现就是信息的合并—— 1 条边的方案和另外一个 1 条边的方案组合成 2 条边的方案，2 条边的方案又和另外一个 2 条边的方案组合成 4 条边的方案，以此类推。（说大白话就差不多是上面的第三段内容）

于是我们只需将 1 个不使用任何魔法的方案，和 k 个一开始就使用一次魔法的方案顺次拼起来即可。（如下图所示）

说明：将 1 到 n 的（可经过重复点的）路径抽象为一条水平线，用红色和黑色分别表示使用/不使用魔法。

因此，对于每条边 (u,v)，我们只需更新以 u 或 v 出发的方案即可。该部分时间复杂度由 O(n^2m) 降为 O(nm)，跑得飞快。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
const int max_n=100+5;
const int max_m=2500+5;
int u[max_m],v[max_m],t[max_m];
long long dis[max_n][max_n],d[max_n][max_n];
const long long inf=1e18;
struct Matrix
{
    long long v[max_n][max_n];
}A,ans;
inline Matrix operator * (const Matrix &a,const Matrix &b)
{
    static Matrix res;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            res.v[i][j]=inf;
            for(int k=1;k<=n;++k)
                res.v[i][j]=min(res.v[i][j],a.v[i][k]+b.v[k][j]);
        }
    return res;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            dis[i][j]=d[i][j]=(i==j?0:inf);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",u+i,v+i,t+i);
        dis[u[i]][v[i]]=t[i];
    }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            ans.v[i][j]=dis[i][j];
    for(int k=1;k<=m;++k)
        for(int i=1;i<=n;++i)
            d[u[k]][i]=min(d[u[k]][i],-t[k]+dis[v[k]][i]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            A.v[i][j]=d[i][j];
    while(k)
    {
        if(k&1)
            ans=ans*A;
        A=A*A;
        k>>=1;
    }
    printf("%lld\n",ans.v[1][n]);
    return 0;
}