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

【BZOJ4773】负环 倍增Floyd

程序员文章站 2022-05-22 15:17:57
...

【BZOJ4773】负环

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

2

题解:我承认最近做矩乘有点多了~

看时间复杂度显然是O(n³㏒n)可以搞的,所以直接上倍增Floyd,具体方法有点像用倍增求LCA。就是先预处理出邻接矩阵的2次方,4次方,2^n次方。。。然后在不断从大到小去试,如果ans*转移矩阵的2^j次方不存在负环,则ans就乘上邻接矩阵的2^j次方,否则不乘。最后只要在乘上邻接矩阵的一次方,就一定会出现负环了

但仔细思考这个方法,发现貌似不满足单调性,也就是可能存在长度为5的负环,却不存在长度为6的负环,因此我们只要连一条从i到i长度为0的边,即让邻接矩阵的map[i][i]=0,就可以使它满足单调性了(其实正常的邻接矩阵都应该这么搞~)

听说O(n³㏒²n)也能过,难道是我的代码自带大常数?跑了7000多ms~

 

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,m,ans;
typedef struct matrix
{
    int v[310][310];
}M;
M f[12],x,y,emp;
M mmul(M a,M b)
{
    M c=emp;
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                c.v[i][j]=min(c.v[i][j],a.v[i][k]+b.v[k][j]);
    return c;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(emp.v,0x3f,sizeof(emp.v));
    f[0]=x=emp;
    int i,a,b,c,j;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        f[0].v[a][b]=c;
    }
    for(i=1;i<=n;i++)    f[0].v[i][i]=x.v[i][i]=0;
    for(j=1;(1<<j)<=n;j++)
        f[j]=mmul(f[j-1],f[j-1]);
    for(j=j-1;j>=0;j--)
    {
        y=mmul(x,f[j]);
        for(i=1;i<=n;i++)
            if(y.v[i][i]<0)  break;
        if(i==n+1)  x=y,ans+=(1<<j);
    }
    if(ans>n)    printf("0");
    else    printf("%d",ans+1);
    return 0;
}