BZOJ_4773_负环_倍增弗洛伊德

BZOJ_4773_负环

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

先开$Logn$个矩阵$dis$，$dis[i][j][k]$表示从$j$到$k$走$2^{i}$条边的最短路。

然后像倍增$lca$那样，再从大到小找到最后一个没有负环的矩阵，再乘一次初始矩阵，判断有没有负环即可。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 350

int f[N][N][20],n,m,L[N];

struct Mat {

    int v[301][301];

    Mat(){memset(v,0x3f,sizeof(v));}

    Mat operator*(const Mat &x)const {

        Mat re;int i,j,k;

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

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

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

                    re.v[i][j]=min(re.v[i][j],v[i][k]+x.v[k][j]);

                }

            }

        }

        return re;

    }

}dis[10];

bool judge(Mat x) {

    int i;

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

        if(x.v[i][i]<0) return 1;

    }

    return 0;

}

int main() {

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

    int i,x,y,z,sum=0;

    Mat tmp;

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

    for(i=2;i<=n;i++) L[i]=L[i>>1]+1;

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

        scanf("%d%d%d",&x,&y,&z);

        dis[0].v[x][y]=z;

    }

    for(i=1;i<=L[n];i++) dis[i]=dis[i-1]*dis[i-1];

    for(i=L[n];i>=0;i--) {

        if(!judge(tmp*dis[i])) {

            tmp=tmp*dis[i]; sum+=(1<<i);

        }

    }

    tmp=tmp*dis[0];

    printf("%d\n",judge(tmp)?sum+1:0);

}

巴特西