BZOJ 4773: 负环 倍增Floyd

现在看来这道题就非常好理解了.

可以将问题转化为求两点间经过 $k$ 个点的路径最小值，然后枚举剩余的那一个点即可.

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 303

#define inf 1000000000

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

namespace IO

{

    char *p1, *p2, buf[100000];

    #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

    int rd() { int x = 0, f = 1;char c = nc();while (c < 48) {if (c == '-')f = -1;c = nc();}while (c > 47) {x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();}return x * f;}

};

int n,m,dis[N][N][10],tmp[2][N][N];

inline void getmin(int &a,int b) { if(b<a)a=b; }

inline int check()

{

    int i;

    for(i=1;i<=n;++i) if(tmp[1][i][i]<0) return 1;

    return 0;

}

int main()

{

    int i,j,k,l,ans=inf;

    // setIO("input");

    n=IO::rd(),m=IO::rd();

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

    {

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

            for(k=0;k<10;++k) dis[i][j][k]=inf;

    }

    for(i=1;i<=n;++i) for(k=0;k<10;++k) dis[i][i][k]=0;

    for(i=1;i<=m;++i)

    {

        int a=IO::rd(),b=IO::rd(),c=IO::rd();

        getmin(dis[a][b][0], c);

    }

    for(l=1;l<10;++l)

    {

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

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

            {

                if(dis[i][k][l-1]==inf) continue;

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

                {

                    if(dis[i][k][l-1]<inf && dis[k][j][l-1]<inf)

                        getmin(dis[i][j][l],dis[i][k][l-1]+dis[k][j][l-1]);

                }

            }

    }

    for(i=1;i<=n;++i) for(j=1;j<=n;++j) tmp[0][i][j]=inf;

    for(i=1;i<=n;++i) tmp[0][i][i]=0;

    int now=0;

    for(l=9;l>=0;--l)

    {

        for(i=1;i<=n;++i) for(j=1;j<=n;++j) tmp[1][i][j]=tmp[0][i][j];

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

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

        {

            if(tmp[0][i][k]==inf) continue;

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

                    getmin(tmp[1][i][j], tmp[0][i][k]+dis[k][j][l]);

        }

        if(check()) getmin(ans,now|(1<<l));

        else

        {

            now|=(1<<l);

            for(i=1;i<=n;++i) for(j=1;j<=n;++j) tmp[0][i][j]=tmp[1][i][j];

        }

    }

    printf("%d\n",ans==inf?0:ans);

    return 0;

}