BZOJ 4773: 负环

倍增floyd
因为答案具有单调性，若所有点数为 \(n\) 的环没有出现负环，那么 \(n-1\) 的环也不会出现负环，那么我们就找出点数最大的非负环，只要再加一个点就能组成负环了。
预处理出 \(f[k][i][j]\) 表示 \(i \to j\) 恰好走了 \(2^k\) 条边的最短路，那么 \(f[k][i][i]\) 这个环上就有 \(2^k\) 个点了。
然后从高到低枚举每一个二进制位，若与当前环大小的矩阵相乘之后出现符号就考虑下一位，否则就加上这个环的大小，并把相乘后矩阵替换为当前矩阵
复杂度 \(O(n^3\log n)\)

#include <bits/stdc++.h>
using namespace std;

const int N = 307;

inline void checkmin(int &a, int b) {
    if (a > b) a = b;
}

int n;

struct Floyd {
    int a[N][N];
    Floyd() {
        memset(a, 0x3f, sizeof(a));
    }
    Floyd operator * (const Floyd &rhs) const {
        Floyd c;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                for (int k = 1; k <= n; k++)
                    checkmin(c.a[i][j], a[i][k] + rhs.a[k][j]);
        return c;
    }
} f[20], x, y;

int main() {
    int m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        f[0].a[u][v] = c;
    }
    for (int i = 1; i <= n; i++)
        f[0].a[i][i] = y.a[i][i] = 0;
    int lg = 0;
    for (int i = 1; (1 << i) <= n; i++)
        f[i] = f[i - 1] * f[i - 1], lg = i;
    int ans = 0;
    for (int i = lg; ~i; i--) {
        x = y * f[i];
        bool flag = 1;
        for (int j = 1; j <= n; j++)
            if (x.a[j][j] < 0) flag = 0;
        if (flag) ans += (1 << i), y = x;
    }
    printf("%d\n", (ans + 1 > n) ? 0 : ans + 1);
    return 0;
}

BZOJ 4773: 负环

原文：https://www.cnblogs.com/Mrzdtz220/p/12275935.html