bzoj2165: 大楼(倍增floyd)

　　题目大意：一个有向图，n(<=100)个点求一条长度>=m(<=10^18)的路径最少经过几条边。

　　一开始以为是矩乘，蓝鹅当时还没开始写，所以好像给CYC安利错了嘿嘿嘿QWQ

　　第一眼看到这题就想到了某题(戳我)，最后只想出一半。。。

　　倍增floyd：f[p][i][j]表示走了2^p条边，从i到j的最长路径，然后则有：f[p][i][j]=max(f[p][i][j],f[p-1][i][k]+f[p-1][k][j]);

　　当跑倍增floyd的时候，1到某个点路径长度>=m则记录p后break。但是这个p只能告诉你答案在2^(p-1)~2^p之间，那到底怎么统计最少经过几条边儿呢？这就是我当时没想出来的>_<。。。

　　看了题解，ciao，sb了QAQ。。。把这个p按高位到低位贪心，新增一个g[i][j]数组表示当前i到j的最长路径，如果1到某个点长度>=m就不记录，否则每次用f[p][i][k]+g[k][j]来更新g数组，并给ans+=1<<p，这样就可以统计出路径<m的答案了，这个时候随便走一步就>=m，所以输出ans+1就行辣！

　　初始化-233333333不够小害我WA了好几次QAQ【于是我就改成了-2333333333333333333嘿嘿嘿

　　然后还学会了新姿势！

try

{

    throw(true);

}catch(bool){}

代码如下：

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#define ll long long

using namespace std;

int n,p,T;

ll f[][][],h[][],g[][],ans,m,x;

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        ans=;

        scanf("%d%lld",&n,&m);

        memset(f,0xef,sizeof(f));

        memset(g,0xef,sizeof(g));

        for(int i=;i<=n;i++)g[i][i]=;

        for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

        scanf("%lld",&x),f[][i][j]=x?x:-;

        try

        {

            for(p=;p<=;p++)

            for(int k=;k<=n;k++)

            for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

            {

                f[p][i][j]=max(f[p][i][j],f[p-][i][k]+f[p-][k][j]);

                if(i==&&f[p][i][j]>=m)throw(true);

            }

        }catch(bool){}

        while(p--)

        {

            for(int i=;i<=n;i++)for(int j=;j<=n;j++)if(i==j)h[i][j]=;else h[i][j]=-;

            try

            {

                for(int k=;k<=n;k++)

                for(int i=;i<=n;i++)

                for(int j=;j<=n;j++)

                {

                    h[i][j]=max(h[i][j],f[p][i][k]+g[k][j]);

                    if(i==&&h[i][j]>=m)throw(true);

                }

                memcpy(g,h,sizeof(g));

                ans+=1ll<<p;

            }catch(bool){}

        }

        printf("%lld\n",ans+);

    }

}

巴特西

bzoj2165: 大楼(倍增floyd)

最新文章

热门文章