题目地址：洛谷：【P2515】[HAOI2010]软件安装 – 洛谷、BZOJ：Problem 2427. — [HAOI2010]软件安装

题目描述

现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。

输入输出格式

输入格式：
第1行：N, M （0<=N<=100, 0<=M<=500）
第2行：W1, W2, … Wi, …, Wn （0<=Wi<=M ）
第3行：V1, V2, …, Vi, …, Vn （0<=Vi<=1000 ）
第4行：D1, D2, …, Di, …, Dn （0<=Di<=N, Di≠i ）

输出格式：
一个整数，代表最大价值

输入输出样例

输入样例#1：

3 10
5 5 6
2 3 4
0 1 1

输出样例#1：

5

题解

i依赖Di可以表示成图上的有向边(Di, i)，而由于强连通分量内部两两互达，一个安装了其他的一定都要被安装，因此可以缩点考虑。缩完点以后的图是一个有向树，考虑找到所有入度为0的点，从虚拟树根0向它连边，DFS跑一遍树形背包，答案就是dp[0][m]。
该树形背包是该点选择才能够继续选择子树，所以默认该点一定被选择，对于点u所有的dp[u][i]（i≥wu）都要被初始化成vu。树形背包的转移方程如下
\displaystyle dp[i][j+w_u] = \max_{(u, v) \in E}\{ dp[u][j+w_u-k] + dp[v][k] \} \ (k \leq j)
枚举从子树选取多少体积的东西转移而来，比较容易理解。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <utility>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 105;

int n, m;

int w[MAXN], v[MAXN], wn[MAXN], vn[MAXN], degn[MAXN];
std::vector<int> gra[MAXN], gran[MAXN];
std::set<std::pair<int, int> > edges;

int dfn[MAXN], low[MAXN], sno[MAXN], clk, scc;
std::stack<int> sta;
bool insta[MAXN];

inline void tarjan(int u) {
    dfn[u] = low[u] = ++clk;
    insta[u] = true; sta.push(u);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        scc++;
        int p;
        do {
            p = sta.top(); sta.pop(); insta[p] = false;
            sno[p] = scc;
            wn[scc] += w[p];
            vn[scc] += v[p];
        } while(p != u);
    }
}

int dp[MAXN][505];

inline void dfs(int u) {
    for(int i = wn[u]; i <= m; i++) {
        dp[u][i] = vn[u];
    }
    for(int i = 0; i < gran[u].size(); i++) {
        int v = gran[u][i];
        dfs(v);
        for(int j = m - wn[u]; j >= 0; j--) {
            for(int k = 0; k <= j; k++) {
                dp[u][j + wn[u]] = std::max(dp[u][j + wn[u]], dp[u][j + wn[u] - k] + dp[v][k]);
            }
        }
    }
}

int di;

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        w[i] = readint();
    }
    for(int i = 1; i <= n; i++) {
        v[i] = readint();
    }
    for(int i = 1; i <= n; i++) {
        di = readint(); if(!di) continue;
        gra[di].push_back(i);
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++) {
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(sno[u] != sno[v] && !edges.count(std::make_pair(sno[u], sno[v]))) {
                gran[sno[u]].push_back(sno[v]); degn[sno[v]]++;
                edges.insert(std::make_pair(sno[u], sno[v]));
            }
        }
    } 
    for(int i = 1; i <= scc; i++) {
        if(!degn[i]) gran[0].push_back(i);
    }
    dfs(0);
    printf("%d", dp[0][m]);
    return 0;
}