P11676 DFS Order 题解

sunkuangzheng · 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";   
}