自动搬运

查看原文

来自洛谷，原作者为

	sunkuangzheng **

搬运于2025-08-24 23:09:24，当前版本为作者最后更新于2025-01-29 12:08:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给定一张 $n(1 \le n \le 750)$ 个点的无向图，可以花费 $a_{i,j}(a_{i,j} \ge 0)$ 的代价修改边 $(i,j)$ 的存在状态，求让 $[1,2,\ldots,n]$ 变成原图一个 DFS 序的最小代价。

首先考虑原图里没有边的部分分，此时最后图的形态一定是一棵树。

注意到 dfs 树的结构是很好的，一个子树内的点集一定是一个连续区间，且没有向外连边。每个子树内部的决策实际上是独立的。令 $f_{l,r}$ 表示以 $l$ 为根的子树包含区间 $[l,r]$ 的最小代价，转移时枚举新加进来的子树 $[k+1,r]$，有 $f_{l,r} \gets f_{l,k} + f_{k+1,r} + a_{l,k+1}$。时间复杂度 $\mathcal O(n^3)$。

考虑现在原图有一些边，我们可以直接将它们全删除，然后将加这条边的代价改成 $-a_{i,j}$。由于存在负边，最终图的形态可能会包含一些返祖边，但是不会包含横插边。 继续使用上述 DP，注意到在把子树 $[k+1,r]$ 加入 $[l,k]$ 时只会增加返祖边 $(l,k+1),(l,k+2),\ldots,(l,r)$，我们把代价是负的加进来即可。前缀和预处理后总复杂度仍然是 $\mathcal O(n^3)$。

/**
 *    author: sunkuangzheng
 *    created: 28.01.2025 13:37:41
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 751;
using namespace std;
int T,n,a[N][N],f[N][N],sm[N][N];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin >> n; int c = 0;
	for(int j = 2;j <= n;j ++) for(int i = 1;i < j;i ++) cin >> a[i][j],
		c += a[i][j] < 0 ? -a[i][j] : 0;
	for(int i = 1;i <= n;i ++) f[i][i] = 0;
	for(int i = 1;i <= n;i ++) for(int j = i + 1;j <= n;j ++)
		sm[i][j] = sm[i][j-1] + (a[i][j] < 0 ? a[i][j] : 0);
	for(int l = 2;l <= n;l ++) for(int i = 1;i + l - 1 <= n;i ++){
		int j = i + l - 1; f[i][j] = 1e9;
		for(int k = i;k < j;k ++)
			f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j] + sm[i][j] - sm[i][k+1] + a[i][k+1]);
	}cout << f[1][n] + c << "\n"; 	
}