题解 AT5147 【[AGC036D] Negative Cycle】

小粉兔 · 2020-02-26 08:25:07 · 题解

考虑差分约束模型，图中不存在负环等价于存在一组合法的差分约束的解。

考虑每个节点作为一个变量，第 i 个节点对应的变量为 x_i。

因为初始的边不能删去，所以一定有 x_i \ge x_{i + 1}。

考虑令 q_i = x_i - x_{i + 1}，那么就会有 q_i \ge 0。

假设保留了一条边权为 -1 的 i \to j 的边，也就是说 i < j 的话：
就会有 x_i - 1 \ge x_j，即 x_i - x_j \ge 1，也就是说 q_i + q_{i + 1} + \cdots + q_{j - 1} \ge 1。

假设保留了一条边权为 1 的 i \to j 的边，也就是说 i > j 的话：
就会有 x_i + 1 \ge x_j，即 x_j - x_i \le 1，也就是说 q_j + q_{j + 1} + \cdots + q_{i - 1} \le 1。

反过来想，如果确定了所有的 q_i，那么每一条边就应该尽可能地保留下来，这样代价最小。

对于边权为 -1 的边，是区间和 \ge 1 才能保留，也就是说如果区间和 = 0 就必须删除。

对于边权为 1 的边，是区间和 \le 1 才能保留，也就是说如果区间和 \ge 2 就必须删除。

也就是说，对于一种 q 的取值方案，q_i = 0 的每个连续段，都对应着一系列的边权为 -1 的边的删除。

而区间和 \ge 2 的区间也对应着边权为 1 的边的删除。

显然可以发现，如果出现了 q_i \ge 2，不如把它变成 1，这样一定会变得更优（边 i \to (i + 1) 不用被删除了）。

所以只需要考虑 q 的取值为 \{0, 1\} 的情况。

然后可以发现，每个 0 的连续段就对应着一部分区间的删除，所以考虑如下 DP：

记 dp(i, j) 表示考虑到了 q_i，最后一个 1 取在了 q_i，倒数第二个 1 取在了 q_j 处的情况下，可以确定的代价的最小值。