洛谷P2515 [HAOI2010]软件安装 题解

题目链接：P2515 [HAOI2010]软件安装

题意：

现在我们的手头有 \(N\) 个软件，对于一个软件 \(i\) ，它要占用 \(W_i\) 的磁盘空间，它的价值为 \(V_i\) 。我们希望从中选择一些软件安装到一台磁盘容量为 \(M\) 计算机上，使得这些软件的价值尽可能大（即 \(V_i\) 的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件 \(j\) （包括软件 \(j\) 的直接或间接依赖）的情况下才能正确工作（软件 \(i\) 依赖软件 \(j\) )。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为 \(0\) 。

我们现在知道了软件之间的依赖关系：软件 \(i\) 依赖软件 \(D_i\) 。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则\(D_i=0\)，这时只要这个软件安装了，它就能正常工作。

输入格式：

第1行：\(N,M(0\leq N\leq 100, 0\leq M\leq 500)\)

第2行：\(W_1,W_2, ... W_i, ..., W_n (0\leq W_i\leq M)\)

第3行：\(V_1, V_2, ..., V_i, ..., V_n (0\leq V_i\leq 1000)\)

第4行：\(D_1, D_2, ..., D_i, ..., D_n (0\leq D_i\leq N, D_i≠i)\)

输出格式：

一个整数，代表最大价值

一看题目给出了一个沙漠，就开始害怕了。其实这题没那么毒瘤（（

显然在一个环里的要么全选，要么都不选

因此我们可以把整个环看作一个点，则原图变成了一个森林

然后就变成了一个树上背包的问题了。

不过森林背包我也没听说过，所以我们建一个必选的（显然）虚点，连接所有的树根结点

然后就是简单的树形dp啦（下文用 \(a\uparrow b+c\) 表示 \(a \gets \max\{a,b+c\}\) ）

设 \(f_{i,j}\) 表示 \(i\) 所在子树的用不超过 \(j\) 的空间能得到的最大价值，则 \[ f_{i,j} \uparrow \max_{j-k \ge w^{\prime}_i \land v \in \mathrm{son}(u)}\{f_{i,j-k} + f_{v,k}\} \] 时间复杂度 \(\mathcal{O}(nm^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(135))
#define M ((int)(515))

bitset<N> ins;
int n,m,pos=1,head[N];
int stktop,tim,scnt,fa[N],w[N],v[N],W[N],V[N];
int in[N],top[N],stk[N],low[N],dfn[N],scc[N],f[N][M];
struct Edge{int u,v,next;} e[M];
void addEdge(int u,int v){ e[++pos] = {u,v,head[u]}; head[u]=pos; }
void Tarjan(int u)
{
    dfn[u] = low[u] = ++tim;
    stk[++stktop] = u; ins[u] = 1;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v;
        if(!dfn[v])
        {
            Tarjan(v); down(low[u], low[v]);
        }else if(ins[v]) down(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        top[++scnt] = u;
        for(int p=0; p!=u; )
        {
            p = stk[stktop--]; ins[p]=0; scc[p]=scnt;
            V[scnt] += v[p]; W[scnt] += w[p];
        }
    }
}
void dfs(int u)
{
    for(int i=W[u]; i<=m; i++) f[u][i]=V[u];
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v; dfs(v);
        for(int j=m; j>=W[u]; j--)
            for(int k=0; j-k >= W[u]; k++)
                up(f[u][j], f[u][j-k] + f[v][k]);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> w[i];
    for(int i=1; i<=n; i++) cin >> v[i];
    for(int i=1; i<=n; i++)
    {
        cin >> fa[i];
        if(fa[i]) addEdge(fa[i], i);
    }
    for(int i=1; i<=n; i++) if(!dfn[i]) Tarjan(i);
    int tmp = pos; pos=1; for(int i=1; i<=n; i++) head[i] = 0;
    for(int i=2; i<=m+1; i++)
    {
        int u = scc[e[i].u], v=scc[e[i].v];
        if(u != v) addEdge(u,v), ++in[v];
    }
    for(int i=1; i<=scnt; i++) if(!in[i]) addEdge(scnt+1, i);
    dfs(scnt+1); cout << f[scnt+1][m] << '\n';
    return 0;
}