「BZOJ2165」大楼
Description
xz是一个旅游爱好者，这次他来到了一座新的城市。城市中央有一幢高耸入云的大楼。这幢楼到底有多少层呢？据说和非负整数的个数是一样多的。xz想爬上这座大楼来观赏新城市的全景。这幢大楼的楼层从下至上用从小到大的非负整数编号。每层楼有n个房间，用1到n的正整数编号。楼层之间用电梯连接，电梯只能上行，不能下行或者同层移动。（下楼一般自行解决）电梯用(u,v,w)的形式给出，表示对于任意正整数i，有第i层的房间u到第i+w层的房间v有一部电梯。电梯只能从起点开往终点，不能中途停留。 xz想要观赏城市全景，至少需要登上第m层楼，即最终需要到达的楼层数≥m。由于乘坐电梯要缴纳高额的费用，而如果花销太大回家就没法报账了，xz希望乘坐电梯的次数最少。现在xz在第0层的1号房间，你需要求出这个最少的乘坐次数。
Input
第一行包含一个正整数T，表示数据的组数。接下来的数据分为T个部分。每个部分第一行包含两个正整数n和m，意义见题目描述。接下来n行，每行包含n个非负整数。这n行中，第i行第j个数为Wi,j，如果wi,j非零，则表示有电梯(i,j,Wi,j)。同一行各个数之间均用一个空格隔开。
Output
对于每组数据，输出一行一个正整数，最少的乘坐次数。
Sample Input
6 147
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3
6 152
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3
Sample Output
10
「样例说明」
第一组数据中，使用电梯的顺序为1→2→3→1→2→3→1→4→6→6；第二组数据中，使用电梯的顺序为1→2→3→1→2→3→1→4→5→4→6。第二组数据最后到达了153层，但是没有更短的路径使得恰好到达152层，因此答案为10。
HINT
有如下几类具有特点的数据： 1、有10%的数据所有的n=2； 2、有20%的数据m≤3000； 3、有20%的数据对于满足1≤i,j≤n的整数i和j，若wi,j≠0，则有wi,j≥1015； 4、有30%的数据所有的n=40。以上各类数据均不包含其他类数据。对于所有数据T=5，1≤n≤100，1≤m≤1018；对于满足1≤i,j≤n的整数i和j，有0≤wi,j≤1018。数据保证能够到达m层或更高的楼层。
题解
f[i][j][p]表示从i到j坐了p次电梯的最大上升高度
f[i][j][p]=max{f[i][k][p/2]+f[k][j][p/2]}
这样就能用矩阵从f1=w得出f2,f4,f8…
直到第一行出现>=m的数停止
问题转化为求fp，p->max，使得第一行都小于m，用二进制拆分的思想从大到小累加
某神犇提出了初始矩阵的设置问题
可以把初始矩阵改成对角线0，其余-INF TAT
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define ll long long #define inf 1e18 using namespace std; ll read() { ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int T; int n,cnt,ans; ll m; struct M{ ll v[105][105]; M(){ memset(v,0,sizeof(v)); } }f[100]; bool jud(M x) { for(int i=1;i<=n;i++) if(x.v[1][i]>=m)return 1; return 0; } M operator*(M a,M b) { M c; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { c.v[i][j]=-1e18; for(int k=1;k<=n;k++) c.v[i][j]=max(c.v[i][j],a.v[i][k]+b.v[k][j]); if(c.v[i][j]>m)c.v[i][j]=m; } return c; } int main() { T=read(); while(T--) { n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { f[1].v[i][j]=read(); if(!f[1].v[i][j])f[1].v[i][j]=-1e18; } for(cnt=1;;cnt++) { f[cnt+1]=f[cnt]*f[cnt]; if(jud(f[cnt+1]))break; } M t=f[1]; ll ans=1; for(int i=cnt;i;i--) { M x=t*f[i]; if(!jud(x)) { for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) t.v[j][k]=x.v[j][k]; ans+=1LL<<(i-1); } } printf("%lld\n",ans+1); } return 0; } |
OI 课件=>
您WA了啊~
妙啊 太妙了orz
表示没有看懂，能解释一下吗？？
转移方程类似矩阵乘法，答案可通过倍增来求