[AGC036D] Negative Cycle
题意：\(n\) 个点的有向图，初始有边 \(i \to i + 1\)，边权为 0，不可删除。有边 \(i \to j(i \neq j)\)，边权为 \(\begin{cases}1, &i > j\\-1, &i<j\end{cases}\)，可删除，删除代价为 \(a_{i, j}\)，你需要删除一些边，使得这张图上没有负环，求最小代价。
\(1 \leq n \leq 500\)
有向图上没有负环，则存在最短路，则差分约束有解。
每个点设变量 \(x_i\)，那么一条 \(i \to j\) 边权为 \(w\) 的边就代表 \(x_j - x_i \leq w\)。
所以初始 \(i \to i + 1\) 的边表示 \(x_i \geq x_{i+1}\)。
设 \(d_i = x_{i-1} - x_i \geq 0\)。
对于边 \(i \to j\)，\(i < j\) 时为第一类边，表示 \(\sum\limits_{k = i + 1}^jd_k \geq 1\)，则对于一串 \(d_k = 0\)上的此类边都需要删除；
\(i > j\) 时为第二类边，表示 \(\sum\limits_{k=i+1}^jd_k \leq 1\)，跨过多于一个1的边需要删除。
设 \(dp(i, j)\) 表示考虑了前 \(i\) 个变量，最后两个 1 分别在 \(i, j\) 的最小代价，用二维前缀和计算区间删边的代价，时间复杂度 \(O(n^3)\)。
void solve() {
int n;
std::cin >> n;
std::vector a(n + 1, std::vector<LL>(n + 1)), b = a;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i < j) {
std::cin >> a[i][j];
} else if (i > j) {
std::cin >> b[i][j];
}
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
}
}
std::vector dp(n + 1, std::vector<LL>(n + 1, 1e18));
for (int i = 0; i <= n; i++) {
dp[i][0] = a[i][i];
for (int j = 1; j < i; j++) {
for (int k = 0; k < j; k++) {
smin(dp[i][j], dp[j][k] + b[i][k] - b[j][k]);
}
dp[i][j] += a[i][i] - a[i][j] - a[j][i] + a[j][j];
}
}
LL ans = 1e18;
for (int i = 0; i < n; i++) {
smin(ans, dp[n][i]);
}
std::cout << ans << "\n";
}最后修改于 2022-01-13