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

BZOJ4773: 负环(倍增Floyd)

程序员文章站 2022-10-16 16:33:22
题意 "题目链接" Sol 倍增Floyd,妙妙喵 一个很显然的思路(~~然而我想不到~~是用$f[k][i][j]$表示从$i$号点出发,走$k$步到$j$的最小值 但是这样复杂度是$O(n^4)$的 考虑倍增优化,设$f[k][i][j]$表示从$i$号点出发,走$2^k$步到$j$的最小值 每 ......

题意

题目链接

sol

倍增floyd,妙妙喵

一个很显然的思路(然而我想不到是用\(f[k][i][j]\)表示从\(i\)号点出发,走\(k\)步到\(j\)的最小值

但是这样复杂度是\(o(n^4)\)

考虑倍增优化,设\(f[k][i][j]\)表示从\(i\)号点出发,走\(2^k\)步到\(j\)的最小值

每次转移相当于把两个矩阵乘起来,复杂度\(o(n^3logn)\)

注意答案不一定有单调性,可以对每个点连一条向自己边权为\(0\)的边,这样就满足单调性了

感觉最近写代码很有手感啊qwq

#include<bits/stdc++.h>
#define chmin(a, b) (a = a < b ? a : b)
using namespace std;
const int maxn = 301;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, base;
struct ma {
    int m[maxn][maxn];
    ma() {
        memset(m, 0x3f, sizeof(m));
    }
    ma operator * (const ma &rhs) const {
        ma ans;
        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++) 
                    chmin(ans.m[i][j], m[i][k] + rhs.m[k][j]);
        return ans;
    }
}f[31], now, nxt;
int main() {
    n = read(); m = read();
    for(int i = 1; i <= m; i++) {
        int x = read(), y = read(), w = read();
        f[0].m[x][y] = w;
    }
    for(int i = 1; i <= n; i++) f[0].m[i][i] = now.m[i][i] = 0;
    for(int i = 1; (1ll << i) <= n; i++) f[i] = f[i - 1] * f[i - 1], base = i;
    int ans = 0;
    for(int i = base; i >= 0; i--) {
        bool flag = 0;
        nxt = f[i] * now;
        for(int j = 1; j <= n; j++) if(nxt.m[j][j] < 0) {flag = 1; break;}
        if(!flag) ans += 1 << i, now = nxt;
    }
    printf("%d", ans + 1 > n ? 0 : ans + 1);
    return 0;
}