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

【bzoj4773】负环 倍增Floyd

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

题目描述

在忘记考虑负环之后,黎瑟的算法又出错了。对于边带权的有向图 G = (V, E),请找出一个点数最小的环,使得
环上的边权和为负数。保证图中不包含重边和自环。

输入

第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

输出

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

样例输入

3 6
1 2 -2
2 1 1
2 3 -10
3 2 10
3 1 -10
1 3 10

样例输出

2


题解

倍增Floyd

先连i->i(0),然后预处理出邻接矩阵以及它的2^n次方,这样v[i][j][k]表示从i到j最多使用2^k条边的最短路径,目的是满足单调性。

然后使用类似于倍增LCA的思想,按k从大到小乘矩阵,若乘完之后出现负环则不乘,否则乘。

这样可以实现:若有解,则此时的答案矩阵一定是最后一个无解情况。

最后将答案乘上原邻接矩阵并判断一下是否有负环即可。

时间复杂度O(n^3logn),一开始写了个O(n^3log^2n)竟然只有14s,改了以后竟然还有9s,不得不吐槽一下。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 310
using namespace std;
int n , log[N];
struct data
{
    int v[N][N];
    data()
    {
        memset(v , 0x3f , sizeof(v));
    }
    data operator*(const data a)const
    {
        data ans;
        int i , j , k;
        for(k = 1 ; k <= n ; k ++ )
            for(i = 1 ; i <= n ; i ++ )
                for(j = 1 ; j <= n ; j ++ )
                    ans.v[i][j] = min(ans.v[i][j] , v[i][k] + a.v[k][j]);
        return ans;
    }
}dis[10] , tmp;
bool judge(data a)
{
    int i;
    for(i = 1 ; i <= n ; i ++ )
        if(a.v[i][i] < 0)
            return 1;
    return 0;
}
int main()
{
    int m , x , y , z , i , sum = 0;
    scanf("%d%d" , &n , &m);
    for(i = 1 ; i <= n ; i ++ ) dis[0].v[i][i] = tmp.v[i][i] = 0;
    for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1;
    while(m -- ) scanf("%d%d%d" , &x , &y , &z) , dis[0].v[x][y] = z;
    for(i = 1 ; i <= log[n] ; i ++ ) dis[i] = dis[i - 1] * dis[i - 1];
    for(i = log[n] ; ~i ; 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);
    return 0;
}