【题意】从第0层开始有无穷层，每层有n个房间，给定矩阵A，A[i][j]表示从第x层的房间 i 可以跳到第x+A[i][j]层的房间 j （x任意），A[i][j]=0表示不能跳。初始在第0层第1个房间，求最少跳几次可以到达>=m层。n<=100,m<=10^18。
【算法】矩阵快速幂
【题解】我的写法好像和网上的不太一样……
设$f_n[i]$表示跳n步在房间 i 的最高层数（这里全部的n和题目的n无关），考虑递推列向量$f_n$，设转移矩阵T，满足$T_{i,j}=A_{j,i}$，那么有：
$$T \times f_n=f_{n+1}$$
初始状态f0={1,0,0…0}，那么写成幂形式：
$$T^n \times f_0=f_n$$
为了方便，容易发现$T^n$的最左一列就是$f_n$。
我们要跳到$f_n$中包含>=m的数字为止，所以预处理所有$T^{2^i}$，倍增即可。
复杂度O(n^3*log m+n log m)。
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=101; const ll inf=1000000000000000000; ll m,c2[N],c[N][N],A[70][N][N],ans[N][N],ans2[N][N]; int n; void multply(ll a[N][N],ll b[N][N],ll d[N][N]){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ c[i][j]=-inf;// for(int k=1;k<=n;k++){ c[i][j]=max(c[i][j],a[i][k]+b[k][j]); } } } for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=c[i][j]; } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%lld",&A[0][j][i]); if(A[0][j][i]==0)A[0][j][i]=-inf; } } int tot=0; bool ok=0; for(int i=1;i<=n;i++)if(A[tot][i][1]>=m){ok=1;break;} if(!ok){ while(1){ tot++; multply(A[tot-1],A[tot-1],A[tot]); bool ok=0; for(int i=1;i<=n;i++)if(A[tot][i][1]>=m){ok=1;break;} if(ok)break; } } c2[0]=1; for(int i=1;i<=tot-1;i++)c2[i]=c2[i-1]*2; ll ANS=c2[tot-1]; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]=A[tot-1][i][j]; for(int i=tot-2;i>=0;i--){ multply(ans,A[i],ans2); bool ok=1; for(int j=1;j<=n;j++)if(ans2[j][1]>=m)ok=0; if(ok){ ANS+=c2[i]; for(int k=1;k<=n;k++)for(int l=1;l<=n;l++)ans[k][l]=ans2[k][l];// } } printf("%lld\n",ANS+1); } return 0; }
View Code
注意T[i][j]=0时设为-inf，即不可达。
网上的角度：关键在于题意的理解……给定n个点的有向图边权矩阵，0表示无边，求最少经过几条边使得路径长度>=m。
经过指定条边后的最长路矩阵是很容易知道的，设$C^x$表示经过x条边后的最长路矩阵，$A$表示有向边权矩阵（0要设为-inf），那么：
$$C^x(i,j)=\max_k\{C^{x-1}(i,k)+A(k,j)\}$$
所以C^x=A^x。
预处理$C^{2^i}$，然后倍增到第一行出现>=m的数字为止。
复杂度O(n^3 log m+n log m)。
转载于:https://www.cnblogs.com/onioncyc/p/8780568.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/101723.html原文链接：https://javaforall.net
