BZOJ4773: 负环(倍增Floyd)
程序员文章站
2022-05-03 18:36:24
题意 "题目链接" 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; }
上一篇: 百度开源的分布式 id 生成器
下一篇: 福州大学算法作业题 - 数列