【bzoj2165】大楼

2015.04.15 09:42 Wed | 19次阅读 | 旧日oi | 固定链接 | 源码

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

2
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

9
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层或更高的楼层。

题解

一种叫做倍增floyd的算法,和矩阵乘法很像
用f[k].m[i][j]表示坐了2^(k-1)次电梯后从i到j的最小乘坐次数。则f[k+1]矩阵就是两个f[k]矩阵相乘就可以了
每次乘完jud一下,如果f[1][i]>=m了,就可以退出了
然后我们利用2进制的思想就可以求出最小步数了

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 1e18
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T,n,cnt;
ll m,ans;
struct Matrix{
    ll a[105][105];
}f[100];
Matrix operator *(Matrix a,Matrix b)
{
    Matrix c;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            c.a[i][j]=-inf;
            for(int k=1;k<=n;k++)
            c.a[i][j]=max(c.a[i][j],a.a[i][k]+b.a[k][j]);
            if(c.a[i][j]>m) c.a[i][j]=m;
        }
    }
    return c;
}
bool jud(Matrix x)
{
    for(int i=1;i<=n;i++)
    if(x.a[1][i]>=m) 
    return 1;
    return 0;
}
int main()
{
    T=read();
    while(T--)
    {
        n=read();m=read();ans=1;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            f[1].a[i][j]=read();
            if(!f[1].a[i][j]) 
            f[1].a[i][j]=-inf;
        }
        for(cnt=1;;cnt++)
        {
            f[cnt+1]=f[cnt]*f[cnt];
            if(jud(f[cnt+1])) 
            break;
        }
        Matrix t=f[1];
        for(int i=cnt;i;i--)
        {
            Matrix x=t*f[i];
            if(!jud(x))
            {
                for(int j=1;j<=n;j++)
                    for(int k=1;k<=n;k++)
                        t.a[j][k]=x.a[j][k];
                ans+=(1ll<<(i-1));
            }
        }
        printf("%lld\n",ans+1);
    }
    return 0;
}```