CF147B 题解

Solution

一道十分典型的 dp 题。有三个关键点分别是定义状态、优化和答案的统计。

• 首先定义状态，定义 \(f_{i,j,p}\) 表示 \(i \to j\) 号节点，共走了不超过 \(p\) 条边，且是 \(i \to j\) 的最长路径。不超过 \(p\) 条边是为了方便转移，而最长路径如果都为负环，说明需要走更多的边，实际上也是为了方便转移。但是这样是 \(O(n^4)\) 转移的，所以用一个很常见的 trick 就是倍增。将状态定义变成这样：\(f_{i,j,p}\) 表示 \(i \to j\) 号节点，共走了不超过\(2^p\) 条边，且是 \(i \to j\) 的最长路径。然后状态转移便是 \(O(n^3\operatorname{log}n)\) 的，状态转移方程为 \(f_{i,j,p}=f_{i,k,p-1}+f_{k,j,p-1}\)，可以类比 Floyd 算法的转移。

• 然后就是统计答案，注意在这时，你需要枚举 \(p\)，如果 \(2^p\) 步可以达到最小正环，便继续考虑 \(2^{p-1}\) 是否可行。如果不行，就累加答案，仍然继续考虑 \(2^{p-1}\)。

注意数组赋成 \(-\infty\) 以及细节的处理。