题解 | #[HAOI2010]软件安装#

没有题解，我就来写个题解，这个题我们分析来看，一个软件会依赖于另一个软件，那如果出现了环，比如 他们互相依赖，所以这个三个要么不选，要么全选，再思考一下，那就是强连通分量里面的所有点，要么全选，要么全不选。那第一步我们肯定进行强连通分量缩点，雨巨姐姐教育我们，强连通分量缩点后会得到什么！有向无环图，题目中还给定了一个条件一个软件最多依赖另外一个软件，我们很兴奋啊，这不就是一棵树了吗，严谨地说应该是森林，那我们的问题就转化成了在森林上求背包问题，考虑表示的状态为，已经选了这个节点上的物品，此时背包容量为。那么转移方程为，为的前驱节点。

下面附上一份我的代码，如有错误欢迎各位大佬在评论区或者私信我指出。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

std::vector<int> e[105], g[105];
int n, m, cnt = 0, num = 0;
int w1[105], v1[105], dfn[105], low[105], col[105], vis[105], w[105], v[105], in[105];
std::stack<int> st;

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    vis[u] = 1;
    st.push(u);

    for (auto v : e[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        }
        else if (vis[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }

    if (low[u] == dfn[u]) {
        num++;
        while (1) {
            int cur = st.top();
            col[cur] = num;
            vis[cur] = 0;
            w[num] += w1[cur];
            v[num] += v1[cur];
            st.pop();
            if (cur == u) break;
        }
    }
}

int dp[105][505];
void dfs(int u) {
    for (int i = w[u]; i <= m; i++) {
        dp[u][i] = v[u];
    }
    for (auto v : g[u]) {
        dfs(v);
        for (int j = m; j >= w[u]; j--) {
            for (int k = 0; k <= j - w[u]; k ++) {
                dp[u][j] = std::max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
    }
}

void solve() {
    std::cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        std::cin >> w1[i];
    }
    for (int i = 1; i <= n; i++) {
        std::cin >> v1[i];
    }

    for (int i = 1; i <= n; i++) {
        int p;
        std::cin >> p;
        if (!p) continue;
        e[p].push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    
    for (int i = 1; i <= n; i++) {
        for (auto v : e[i]) {
            int x = col[i], y = col[v];
            if (x != y) {
                g[x].push_back(y);
                in[y]++;
            }
        }
    }

    for (int i = 1; i <= num; i++) {
        if (!in[i]) {
            g[n + 1].push_back(i);
        }
    }

    dfs(n + 1);
    int ans = 0;
    for (int i = 0; i <= m; i++) {
        ans = std::max(ans, dp[n + 1][i]);
    }
    std::cout << ans << '\n';
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}