BZOJ4773: 负环(倍增Floyd)

题意

题目链接

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;

}

巴特西

BZOJ4773: 负环(倍增Floyd)

题意

Sol

最新文章

热门文章