这篇文章上次修改于 464 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 1627 个字，阅读时长 ≈ 5 分钟

BZOJ 2165. 大楼

题目链接

题意

从第0层开始有无穷层，每层有n个房间，给定矩阵A，$A_{i,j}$ 表示从第x层的房间 i 可以跳到第 $x+A_{i,j}$ 层的房间 j（x任意），$A_{i,j}=0$ 表示不能跳。初始在第0层第1个房间，求最少跳几次可以到达 $\geq m$ 层。

思路

首先想直接暴力枚举最后答案，但一看 $m\leq 1e18$ 暴力枚举直接爆炸，想想怎么加速枚举，倍增，枚举 $k$ 代表跳 $2^k$ 次，加上起点终点我们可以设出一个 $f[k][i][j]$ 表示跳了 $2^k$ 步，最后一步从点 i 跳到点 j 能跳到的最大高度。

以下内容节选自此博客：

由于我们从任意一个 $i$ 递推到 $i−1$ 进行的都是相同的操作，而整个递推过程具备单调性，根据转移方程定义的运算满足结合律，因此我们可以采用一种类似于矩阵乘法的倍增算法。

定义状态 $g(p,i,j)$ 表示从房间 $i$ 走到 $j$，走不超过 $2p$ 步到达的最高层数。转移如下：

$g(p,i,j)=\begin{cases}g(p-1,i,j)\\\max\limits_{k=1}^n\Big\{g(p-1,i,k)+g(p-1,k,j)\Big\}\end{cases}\Bigg\}$

由于所有的边消耗的步数都为一步，因此上述倍增算法一定可以包含不超过 $2p$ 的所有情况。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<climits>
using namespace std;
typedef long long ll;
ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3ll)+(x<<1ll)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=102;
const ll inf=1ll<<60;
int T,n,h,t,cnt;
ll ans,m;
struct jz{
    ll mt[N][N];
    jz(){
        for(int i=0;i<N-1;++i) for(int j=0;j<N-1;++j) mt[i][j]=0;
    }
    jz operator *(const jz &x)const{
        jz c;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                c.mt[i][j]=-inf;
                for(int k=1;k<=n;++k)
                    c.mt[i][j]=max(c.mt[i][j],mt[i][k]+x.mt[k][j]);
            }
        return c;
    }
}a,f[N];
bool check(jz x){
    for(int i=1;i<=n;++i) if(x.mt[1][i]>=m) return 1;
    return 0;
}
int main()
{
    T=(int)read();
    while(T--){
        n=(int)read();
        m=read();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                //初始化+读入
                f[1].mt[i][j]=read();
                if(!f[1].mt[i][j]) f[1].mt[i][j]=-inf;
            }
        ans=1;
        for(cnt=1;cnt<N-1;++cnt){
            //倍增预处理
            f[cnt+1]=f[cnt]*f[cnt];
            if(check(f[cnt+1])) break;
        }
        a=f[1];
        bool flag=0;
        for(int i=cnt;i;--i){
            //统计答案
            jz b=a*f[i];
            if(!check(b)){
                a=b;
                ans+=(1ll<<(i-1));
            }
            else flag=1;
        }
        if(flag) printf("%lld\n",ans+1);
        else printf("-1\n");
    }
    return 0;
}