题目大意
给定一个 $n$ 个点 $m$ 条边的带权有向图，问图中最短的负环的长度。
数据范围：$n \le 300$。
思路分析
令 $\text{dp}(k, i, j)$ 表示从 $i$ 走 $k$ 步到 $j$，经过的边权和的最小值。我们暴力地对它进行转移，$k$ 每次加一时我们都要使用一次类似矩阵乘法的操作（将乘号换成加号，将求和换成取 $\max$）。我们一直进行转移，直到存在 $\text{dp}(k, i, i) < 0$ 时我们就找到了一个长度为 $k$ 的负环。时间复杂度 $O(n^4)$，不足以通过本题。
但是我们发现矩阵乘法是可以通过倍增的方法优化的。我们令 $\text{dp}(k, i, j)$ 表示从 $i$ 走 $2^k$ 步到 $j$，经过的边权和的最小值。这样我们就可以倍增地在 $O(n^3 \log n)$ 的时间内算出所有这样的矩阵。
在计算答案的时候，我们使用类似倍增找 LCA 的方法，按 $k$ 由大到小的顺序贪心地尝试乘上当前答案矩阵，再看结果矩阵是否有 $\text{dp}(i, i) < 0$。如果没有，则这次尝试是成功的。最后输出一共乘上矩阵的次数 $+1$ 即可。时间复杂度 $O(n^3 \log n)$。
代码实现
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | const int maxn = 300, logn = 8, inf = 1e9 + 1; |
6 | int n, m, f[logn + 3][maxn + 3][maxn + 3], g[maxn + 3][maxn + 3], t[maxn + 3][maxn + 3]; |
7 | |
8 | int main() { |
9 | scanf("%d %d", &n, &m); |
10 | for (int i = 1; i <= n; i++) { |
11 | for (int j = 1; j <= n; j++) { |
12 | f[0][i][j] = g[i][j] = (i == j ? 0 : inf); |
13 | } |
14 | } |
15 | for (int i = 1, u, v, w; i <= m; i++) { |
16 | scanf("%d %d %d", &u, &v, &w); |
17 | if (w < f[0][u][v]) { |
18 | f[0][u][v] = w; |
19 | } |
20 | } |
21 | for (int d = 1; d <= logn; d++) { |
22 | for (int i = 1; i <= n; i++) { |
23 | for (int j = 1; j <= n; j++) { |
24 | f[d][i][j] = inf; |
25 | for (int k = 1; k <= n; k++) { |
26 | f[d][i][j] = min(f[d][i][j], f[d - 1][i][k] + f[d - 1][k][j]); |
27 | } |
28 | } |
29 | } |
30 | } |
31 | int ans = 0; |
32 | bool ok = false; |
33 | for (int d = logn; ~d; d--) { |
34 | bool flag = false; |
35 | for (int i = 1; i <= n; i++) { |
36 | for (int j = 1; j <= n; j++) { |
37 | t[i][j] = inf; |
38 | for (int k = 1; k <= n; k++) { |
39 | t[i][j] = min(t[i][j], g[i][k] + f[d][k][j]); |
40 | } |
41 | if (i == j && t[i][j] < 0) { |
42 | flag = true; |
43 | break; |
44 | } |
45 | } |
46 | if (flag) { |
47 | break; |
48 | } |
49 | } |
50 | if (!flag) { |
51 | ans += 1 << d; |
52 | for (int i = 1; i <= n; i++) { |
53 | for (int j = 1; j <= n; j++) { |
54 | g[i][j] = t[i][j]; |
55 | } |
56 | } |
57 | } else { |
58 | ok = true; |
59 | } |
60 | } |
61 | printf("%d\n", ok ? ans + 1 : 0); |
62 | return 0; |
63 | } |