欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[BZOJ4773]负环

程序员文章站 2022-05-22 15:06:25
...

[BZOJ4773]负环

题目大意:

给定一个\(n(n\le300)\)个点的简单有向图,求经过点数最小的负环。

思路:

\(f[k][i][j]\)表示从\(i\)\(j\),经过至多\(2^k\)条边时,边权和的最小值,然后二分即可。

时间复杂度\(\mathcal O(n^3\log n)\)

源代码:

#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
    register char ch;
    register bool neg=false;
    while(!isdigit(ch=getchar())) neg|=ch=='-';
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return neg?-x:x;
}
const int N=301,K=10;
int n,m,f[K][N][N],tmp[2][N][N];
inline void upd(int &a,const int &b) {
    a=std::min(a,b);
}
inline void reset(int f[N][N]) {
    for(register int i=1;i<=n;i++) {
        for(register int j=1;j<=n;j++) {
            f[i][j]=i==j?0:INT_MAX;
        }
    }
}
inline void copy(int f[N][N],int g[N][N]) {
    for(register int i=1;i<=n;i++) {
        for(register int j=1;j<=n;j++) {
            g[i][j]=f[i][j];
        }
    }
}
inline bool check() {
    for(register int i=1;i<=n;i++) {
        if(tmp[1][i][i]<0) return true;
    }
    return false;
}
signed main() {
    n=getint(),m=getint();
    reset(f[0]);
    for(register int i=0;i<m;i++) {
        const int u=getint(),v=getint();
        f[0][u][v]=getint();
    }
    for(register int l=1;l<K;l++) {
        copy(f[l-1],f[l]);
        for(register int k=1;k<=n;k++) {
            for(register int i=1;i<=n;i++) {
                if(f[l-1][i][k]==INT_MAX) continue;
                for(register int j=1;j<=n;j++) {
                    if(f[l-1][k][j]==INT_MAX) continue;
                    upd(f[l][i][j],f[l-1][i][k]+f[l-1][k][j]);
                }
            }
        }
    }
    int ans=INT_MAX;
    reset(tmp[0]);
    for(register int l=K-1,now=0;l>=0;l--) {
        reset(tmp[1]);
        copy(tmp[0],tmp[1]);
        for(register int k=1;k<=n;k++) {
            for(register int i=1;i<=n;i++) {
                if(tmp[0][i][k]==INT_MAX) continue;
                for(register int j=1;j<=n;j++) {
                    if(f[l][k][j]==INT_MAX) continue;
                    upd(tmp[1][i][j],tmp[0][i][k]+f[l][k][j]);
                }
            }
        }
        if(check()) {
            ans=std::min(ans,now|(1<<l));
        } else {
            now|=1<<l;
            copy(tmp[1],tmp[0]);
        }
    }
    printf("%d\n",ans==INT_MAX?0:ans);
    return 0;
}