AGC036D Negative Cycle 做题记录

有一个 $n$ 个点的带权有向图，刚开始：

• $\forall 1\le i<n$ 存在边 $i\to i+1$，边权为 $0$，这些边不可删除；
• $\forall 1\le i<j\le n$，存在边 $i\to j$，边权为 $-1$；
• $\forall 1\le i<j\le n$，存在边 $j\to i$，边权为 $1$；

给定 $n\times n$ 的正整数矩阵 $A$，删除可删除的 $i\to j$ 的有向边的代价为 $A_{i,j}$，求最小的代价使得图中不存在负环。

$1\le n\le 500$。

做法 1

性质

对于一条 $x\to y$ 的负边，若其最后没有删除，则显然 $\forall i\le x,y\le j$ 的负边 $i\to j$ 都不会被删除。

所以最终负边肯定形如：

• 将序列划分为若干个区间和一些孤立点；
• 一个区间中的点向后面区间中的所有点连负边，孤立点不连负边；

然后正边就不能跨越一整个区间。

那么不难发现将孤立点并入旁边的某个区间是不劣的，因为这不会影响正边的连法，还会减少删边的代价。

所以直接设 $f_{i,j}$ 表示考虑了前 $i$ 个点，上一个区间是 $[j,i]$ 的最小代价，转移直接考虑枚举下一个区间 $[i+1,r]$ 然后用前缀和计算代价即可。

复杂度 $O(n^3)$。

做法 2

性质

一个从 $1$ 可以到达任意点的图不存在负环，当且仅当存在从 $1$ 到任意点 $i$ 的最短路 $d_i$ 存在。

那么考虑 $d_i$ 的限制：

• $d_i\ge d_{i+1}$，这是因为存在边权为 $0$ 的边 $i\to i+1$；
• 对于一条负边 $i\to j$，$d_i-1\ge d_j$；
• 对于一条正边 $j\to i$，$d_i\le d_j+1$；

那么划分出若干个区间满足内部的 $d$ 相等，则后面部分和第一个做法一样了。

复杂度 $O(n^3)$。