洛谷 P2515 软件安装
题意
现在我们的手头有 \(N\) 个软件，对于一个软件 \(i\)，它要占用 \(W_i\) 的磁盘空间，它的价值为 \(V_i\)。我们希望从中选择一些软件安装到一台磁盘容量为 \(M\) 计算机上，使得这些软件的价值尽可能大（即 \(V_i\) 的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件 \(i\) 只有在安装了软件 \(j\)（包括软件 \(j\) 的直接或间接依赖）的情况下才能正确工作（软件 \(i\) 依赖软件 \(j\))。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为 \(0\)。
我们现在知道了软件之间的依赖关系：软件 \(i\) 依赖软件 \(D_i\)。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则 \(D_i=0\)，这时只要这个软件安装了，它就能正常工作。
思路
先强连通分量缩点。
如果一个子图互相依赖，要么就全装，要么就全不装。
由于原图每个点入度为 \(1\)，是一个外向基环树森林，缩点后为一个森林。
添加超级源点连向每个根节点，然后跑一遍树形背包即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, w[N], v[N];
vector <int> E[N];
int low[N], dfn[N], cnt;
bool instk[N];
int stk[N], top, in[N];
int sc, scc[N], W[N], V[N];
int dp[N][N];
bool e[N][N];
void tarjan(int x) {
low[x] = dfn[x] = ++ cnt;
stk[++ top] = x; instk[x] = 1;
for (auto y : E[x]) {
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if (instk[y])
low[x] = min(low[x], dfn[y]);
}
if (low[x] == dfn[x]) {
sc ++;
while (top && stk[top] != x) {
scc[stk[top]] = sc;
instk[stk[top]] = 0;
W[sc] += w[stk[top]];
V[sc] += v[stk[top]];
top --;
}
scc[stk[top]] = sc;
instk[stk[top]] = 0;
W[sc] += w[stk[top]];
V[sc] += v[stk[top]];
top --;
}
}
void dfs(int x) {
dp[x][W[x]] = V[x];
for (int i = 0; i <= sc; i ++) {
if (!e[x][i]) continue;
dfs(i);
for (int j = m; j >= W[x]; j --)
for (int k = 0; k <= j - W[x]; k ++)
dp[x][j] = max(dp[x][j], dp[x][j - k] + dp[i][k]);
}
}
int main() {
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, d; i <= n; i ++) cin >> d, E[d].push_back(i);
for (int i = 1; i <= n; i ++) {
if (dfn[i]) continue;
tarjan(i);
}
for (int i = 1; i <= n; i ++)
for (auto j : E[i])
if (scc[i] != scc[j])
e[scc[i]][scc[j]] = 1,
in[scc[j]] ++;
for (int i = 1; i <= sc; i ++)
if (!in[i]) e[0][i] = 1;
dfs(0);
cout << dp[0][m] << "\n";
return 0;
}