自动搬运

查看原文

来自洛谷，原作者为

	lcjqwq 赠你满天星

搬运于2025-08-24 21:38:33，当前版本为作者最后更新于2018-07-26 18:31:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

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

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

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

Solution

明显是树形dp。设$dp[i][j]$为以$i$号点为根的子树中用不超过$j$的空间的最大价值。

但是这道题所给出的条件不能直接构成一棵树，比如$d[1]=2,d[2]=3,d[3]=1$这时$1,2,3$便形成一个独立的联通块并且构成环。又由于这个环也很特殊：要么都选，要么都不选，所以可以用tarjan将环缩点。新点的$w=\sum\limits_{e \in \text{该环}}w[e]$，$v=\sum\limits_{e \in \text{该环}}v[e]$。

缩点后将原来的联通块之间的边连好后再从$0$向每一个加完边后入度为$0$的点连一条边，此时就将原图转换为一颗以$0$为根的树，然后就可以愉快的树形dp辣。

举个栗子：

如果最开始图是这样的

然后缩点，将$1,2,3$缩为$14$，$10,11,12,13$缩为$15$，然后让$0$向几个联通块连边：

这时原图被转换成对答案等价的一棵树，然后$dfs$用上述方程进行简单的树上背包就解决了。

code

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAXN = 505;
int n, m, cnt, w[MAXN], a[MAXN], d[MAXN]; 
int dfn[MAXN], low[MAXN], bel[MAXN], tot, scc, ins[MAXN], sta[MAXN], top; 
int W[MAXN], V[MAXN], indeg[MAXN], dp[MAXN][MAXN];
struct edge {
    int v;
    edge *next;
}pool[MAXN * 2], *head[MAXN];
inline void addedge(int u, int v) {
    edge *p = &pool[++cnt];
    p->v = v, p->next = head[u], head[u] = p; 
}
void tarjan(int u) {
    dfn[u] = low[u] = ++tot; sta[++top] = u; ins[u] = 1;
    for(edge *p = head[u]; p; p = p->next) {
        int v = p->v;
        if(!dfn[v]) {
            tarjan(v); 
            low[u] = min(low[u], low[v]);
        } else if(ins[v]) 
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]) {
        ++scc;
        while(sta[top + 1] != u) {
            bel[sta[top]] = scc;
            W[scc] += w[sta[top]]; 
            V[scc] += a[sta[top]];
            ins[sta[top--]] = 0;
        }
    }
}
void solve(int u) {
    for(int i = W[u]; i <= m; i++)
        dp[u][i] = V[u];
    for(edge *p = head[u]; p; p = p->next) {
        int v = p->v;
        solve(v); int k = m - W[u];
        for(int i = k; i >= 0; i--) 
            for(int j = 0; j <= i; j++)
                dp[u][i + W[u]] = 
                max(dp[u][i + W[u]], 
                dp[v][j] + dp[u][i + W[u] - j]);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) {
    	scanf("%d", &d[i]); if(d[i]) addedge(d[i], i);
    }
    for(int i = 1; i <= n; i++)    
        if(!dfn[i]) tarjan(i);
    for(int i = 0; i <= n; i++) head[i] = NULL; cnt = 0;
    for(int i = 1; i <= n; i++)
    	if(bel[d[i]] != bel[i]) {
    		addedge(bel[d[i]], bel[i]);
    		indeg[bel[i]]++;
        }
    for(int i = 1; i <= scc; i++) 
        if(!indeg[i]) addedge(0, i);
    solve(0);
    printf("%d\n", dp[0][m]);
 	return 0;
}