题解 P11676

· · 题解

感觉是很优美的题。

先看部分分：所有 a_{i,j}>0，这意味着图初始时无边。那贪心地想肯定是要建出一棵树出来。如何保证一棵树存在一个拓扑序为 [1,n] 呢？如果给出树，想要 check 是好办的，按照顺序能走就走即可。但是这一方向不利于我们构造。

从构造的角度来说，首先要考虑到 dfs 序的一些基本性质，诸如第一个元素为 dfs 树的根，最后一个元素一定是叶子等等。那么这棵树的根首先需要是 1，1 的下面需要下挂一些儿子，因为一棵子树的 dfs 序是连续的，所以将儿子们的 dfs 序依次排开就是 [2,p_1],[p_1+1,p_2],\cdots, [p_{k-1}+1,p_k]，可以拼成 [2,n]。这样的段式结构启发我们进行 dp。

设 f_{l,r} 为建出 dfs 序区间 [l,r] 的一棵树的最小代价，类比上述过程，l 一定是根，枚举最后一个儿子的分界点 j=p_{k-1}+1，对 f_{l,r} 的贡献是 f_{l,j-1}+f_{j,r}+a_{l,j}，最后一项即将根和这个儿子连接起来的代价。复杂度 O(n^3)，可以通过该部分分。

现在图上多了一些边出来，也就是 dfs 树上有些边已经存在了，这时不用算贡献。还有情况是多了一些非树边。我们需要保证他还是一棵 dfs 树，众所周知这一条件等价于不存在横插边，或者说非树边都是返祖边。在 dp 的时候我们要删去横插边。但是这些边的贡献不好统计。不妨容斥一下计算返祖边，返祖边端点一定存在祖先关系，我们将其挂在深度较小处统计。怎么在 dp 时计算呢？考虑点 x 伸出去的边 (x,z) 满足 z 不是 x 儿子的都是返祖边，x 为根时在枚举每个儿子的同时可以得到子树内非儿子的点，形成了一些区间，也就是上面所说的 (p_i+1,p_i]。预处理时做前缀和即可 O(1) 计算，复杂度是 O(n^3)，可以通过。

#include <bits/stdc++.h>
using namespace std;
namespace Le0{
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define db double
#define _int __int128
#define vi vector<int>
#define tii tuple<int,int,int>
const int N=755,inf=0x3f3f3f3f;
const ll lnf=1e18;
int n;
int a[N][N],f[N][N],sm[N][N];
bool vis[N][N];
int sol(int l,int r){
    if(vis[l][r]) return f[l][r];
    vis[l][r]=1;
    if(l==r) return f[l][r]=0;
    if(l>r) return f[l][r]=inf;
    f[l][r]=inf;
    for(int k=l;k<r;k++){
        f[l][r]=min(f[l][r],sol(l,k)+sol(k+1,r)+a[l][k+1]-(sm[l][r]-sm[l][k+1]));
    }
    return f[l][r];
}
void sv(){
    cin>>n;
    int tot=0;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            cin>>a[j][i];
            a[i][j]=a[j][i];
            if(a[i][j]<0) tot-=a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            sm[i][j]=sm[i][j-1]+(a[i][j]<0?-a[i][j]:0);
        }
    }
    int v=sol(1,n);
    cout<<v+tot<<'\n';
}
int main(){
    // int _T;cin>>_T;
    // while(_T--){
        sv();
    // }
    return 0;
}
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    return Le0::main();
}