也就是要避免 \(1\to v\) 的负环。看到负环就往二分 x 的方向去想了，但这样是错的；或者一些暴力的 DP 方法（ \(f(i,j,k)\) 表示 \(i\to j,add-sub=k\) 的最短路）
但正解是模拟 Bellman-Ford 判负环，求松弛 \(n-1\) 与 \(n\) 的结果上的差别，列出不等式。
也许这类 \(n\) 较小的题可以从最暴力最基础的想法出发，比如上次某个 \(n^2\) 条特殊边，暴力跑 dijk 的题。
2024-02-07 23:16:17
也就是要避免 \(1\to v\) 的负环。看到负环就往二分 x 的方向去想了，但这样是错的；或者一些暴力的 DP 方法（ \(f(i,j,k)\) 表示 \(i\to j,add-sub=k\) 的最短路）
但正解是模拟 Bellman-Ford 判负环，求松弛 \(n-1\) 与 \(n\) 的结果上的差别，列出不等式。
也许这类 \(n\) 较小的题可以从最暴力最基础的想法出发，比如上次某个 \(n^2\) 条特殊边，暴力跑 dijk 的题。