ABC236G题解

推销自己的矩阵优化文章：矩阵快速幂优化DP

---

注意到点数及其小，边数也算小，而$L$ 极大，有一股浓烈的矩阵快速幂优化的味道。

首先这个问题肯定是一个 DP 的题，我们有一个暴力的想法，我们对于每一个操作，利用 Floyd 的 DP 思想，邻接矩表示图两点之间经过$1$ 条边的路径数量这个特点，对于每一个操作我们更新邻接矩阵，让后在上面跑矩阵快速幂，幂$L$ 次后的邻接矩阵代表的就是经过$L$ 条边的信息，一次次更新答案判断可达性即可，时间复杂度$O(T n^3 \log L)$，不能通过。

我们考虑如何优化，根据题意，每一次操作只会添加一条边，而要求的是求经过边中操作编号更靠后（也就是更大）的边。我们可以将这个操作编号绑到边权上，那么实际上我们就是要对经过的边的边权取$\max$ 操作。

那么我们有一个显而易见的状态，设$f(i,j,k)$ 表示在从$i$ 到$j$ 节点，经过$k$ 条边的最大边权，转移如下：

$$f(i,j,k)=\min\left\{ \max_{p=1}^{n} f(i,p,k-1)+w(p,j) \right\}$$

其中$w(i,j)$ 表示从$i\rightarrow j$ 边的边权。

考虑这个能不能转成广义矩阵乘法的形式，检验如下：

• 外部加法结合交换律：$\min$ 满足结合律交换律。
• 内部乘法结合律：$\max$ 满足结合律与交换律。
• 分配律：左分配为：$\max(a,\min(b,c))=\min(\max(a,b),\max(a,c))$，由于$\max$ 有交换律所有右分配律同样成立，故分配律成立。

注意转矩阵乘法后千万不要思维定势，各个特殊乘法加法的单位元都是不一样的，下面给出一张图给出了各个广义矩阵乘法对应的单位元：

注意到这个矩阵幂的形式其实和上面 Floyd 的形式差不太多，我们在实现的时候还是邻接矩阵，每个操作的边的边权设为$i$，跑矩阵快速幂即可。时间复杂度$O(n^3 \log L)$，代码如下，跑的很慢大常数选手非我莫属 www。

#include<bits/stdc++.h>
#include <cmath>
#define int long long
using namespace std;
constexpr int MN=250,INF=1e18;
int n,t,l;

struct Matrix{
    int mat[MN][MN];

    Matrix(int x=INF){
        for(int i=0;i<MN;i++){
            for(int j=0;j<MN;j++){
                mat[i][j]=INF;
            }
        }
        if(x==INF) return;
        for(int i=0;i<MN;i++) mat[i][i]=x;
    }

    Matrix operator*(const Matrix &x)const{
        Matrix ret;
        for(int i=0;i<MN;i++){
            for(int j=0;j<MN;j++){
                for(int k=0;k<MN;k++){
                    ret.mat[i][j]=min(ret.mat[i][j],max(mat[i][k],x.mat[k][j]));
                }
            }
        }
        return ret;
    }
}adj;

Matrix ksm(Matrix a,int b){
    Matrix ret(0);
    while(b){
        if(b&1) ret=ret*a;
        a=a*a;
        b>>=1;
    }
    return ret;
}

signed main(){
    cin>>n>>t>>l;
    for(int i=1;i<=t;i++){
        int u,v;
        cin>>u>>v;
        adj.mat[u][v]=i;
    }
    adj=ksm(adj,l);
    for(int i=1;i<=n;i++){
        cout<<(adj.mat[1][i]==INF?-1:adj.mat[1][i])<<'\n';
    }
    return 0;
}