bzoj 4773: 负环——倍增-白红宇

bzoj 4773: 负环——倍增

阅读量：5987 次

发布时间：2019-06-20

本文共 1731 字，大约阅读时间需要 5 分钟。

Description

在忘记考虑负环之后，黎瑟的算法又出错了。对于边带权的有向图 G = (V, E)，请找出一个点数最小的环，使得

环上的边权和为负数。保证图中不包含重边和自环。

Input

第1两个整数n, m,表示图的点数和边数。

接下来的m行，每<=三个整数ui, vi, wi，表<=有一条从ui到vi，权值为wi的有向边。

2 <= n <= 300

0 <= m <= n(n <= 1)

1 <= ui, vi <= n

|wi| <= 10^4

Output

仅一行一个整数，表示点数最小的环上的点数，若图中不存在负环输出0。

Sample Input

3 6

1 2 -2

2 1 1

2 3 -10

3 2 10

3 1 -10

1 3 10

Sample Output

—————————————————————————

f[i][j][k]=mins(f[i-1][a][c]+f[1][c][b]) 转移过来

但是这样其实有点慢我们可以跑一波倍增来确定答案

#include
       
        #include
        
         #include
         
          #include
          
           using std::min;const int M=357;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
     if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;} typedef int mat[M][M];mat f[15],ly,now;int n,m,ans;bool pd(mat s){    for(int i=1;i<=n;i++)if(s[i][i]<0) return 1;    return 0;}void mins(int &x,int y){
     if(x>y) x=y;} int main(){    int x,y,w;    n=read(); m=read();    memset(f,0x3f,sizeof(f));    for(int i=1;i<=n;i++) f[0][i][i]=0;    for(int i=1;i<=m;i++) x=read(),y=read(),w=read(),mins(f[0][x][y],w);    for(int i=1;i<=8;i++){        for(int a=1;a<=n;a++)        for(int c=1;c<=n;c++)        for(int b=1;b<=n;b++)        mins(f[i][a][b],f[i-1][a][c]+f[i-1][c][b]);    }    if(!pd(f[8])) return puts("0"),0;    memset(ly,0x3f,sizeof(mat));    for(int i=1;i<=n;i++) ly[i][i]=0;    for(int i=8;i>=0;i--){        memset(now,0x3f,sizeof(mat));        for(int a=1;a<=n;++a)        for(int c=1;c<=n;++c)        for(int b=1;b<=n;++b)        mins(now[a][b],f[i][a][c]+ly[c][b]);        if(!pd(now)){            ans|=1<