NC19981 [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 ≤ N ≤ 100, 0 ≤ M ≤ 500）\)
第\(2\)行：\(W_1, W_2, ... W_i, ..., W_n (0 ≤ W_i ≤ M)\)
第\(3\)行：\(V_1, V_2, ..., V_i, ..., V_n (0 ≤ V_i ≤ 1000)\)
第\(4\)行：\(D_1, D_2, ..., D_i, ..., D_n (0 ≤ D_i ≤ N, D_i≠i)\)
输出描述:
一个整数，代表最大价值。
示例1
输入
3 10
5 5 6
2 3 4
0 1 1
输出
5
二、解题思路
一个软件最多依赖另外一个软件，把被别人依赖的某个软件向依赖它的软件连上一条有向边，可以得出，每个点的入度均为\(1\)，这是啥？一棵树啊。
然而这样想就出现了问题，万一有环呢？好说，把环给缩掉就行了。我们把新出现的一个森林连上一个共同的虚根\(0\)，构成一颗树，于是问题就转换成了树形\(DP\)
注：容易忽略的情况就是，即使出现环也可以整个环都安装。然后原图如果出现环，这个环必然作为 起点，且这个环不会延申到其他环里。同样地环要么全部装要么全部不装
状态表示
\(f[i][j]\)代表以\(i\)为根的树，在容量为\(j\)的时候，没有处理它的根，所得到的最大价值。
状态转移
\[\large f[i][j]=max(f[i][j],f[i−k][j]+f[son][k−w[son]]+v[son]) \]\(Code\)
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int M = 510;
// 链式前向星
int e[M], h1[N], h2[N], idx, w[M], ne[M];
void add(int h[], int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int n, m;
int W1[N], V1[N];
int W2[N], V2[N], in[N];
int f[N][M]; // 以i为根(不装)的子树装j时的最大价值
// tarjan算法求强连通分量
int stk[N], top; // tarjan算法需要用到的堆栈
bool in_stk[N]; // 是否在栈内
int dfn[N]; // dfs遍历到u的时间
int low[N]; // 从u开始走所能遍历到的最小时间戳
int ts; // 时间戳,dfs序的标识,记录谁先谁后
int id[N], scc_cnt; // 强连通分量块的最新索引号
int sz[N]; // sz[i]表示编号为i的强连通分量中原来点的个数
void tarjan(int u) {
dfn[u] = low[u] = ++ts;
stk[++top] = u;
in_stk[u] = 1;
for (int i = h1[u]; ~i; i = ne[i]) {
int v = e[i];
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stk[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++scc_cnt; // 强连通分量的序号
int x; // 临时变量x,用于枚举栈中当前强连通分量中每个节点
do {
x = stk[top--]; // 弹出节点
in_stk[x] = 0; // 标识不在栈中了
id[x] = scc_cnt; // 记录每个节点在哪个强连通分量中
sz[scc_cnt]++; // 这个强连通分量中节点的个数+1
//===========下面两句是本题特殊的地方================
W2[scc_cnt] += W1[x]; // 记录每个SCC的累加体积和累加价值
V2[scc_cnt] += V1[x];
} while (x != u);
}
}
// 以dfs方式完成树形dp汇总
void dfs(int u) {
// ① DP初始化
// 对于以u为根的子树而言，如果剩余空间能够装得下u,那么最少将获取到V2[u]的价值
for (int i = W2[u]; i <= m; i++) f[u][i] = V2[u];
for (int i = h2[u]; ~i; i = ne[i]) {
int v = e[i];
dfs(v); // 先填充儿子，再回填充父亲
// ② 有树形背包，有依赖的背包
for (int i = m; i >= W2[u]; i--) // 枚举每个可能的空间
for (int j = 0; j + W2[u] <= i; j++) // 准备给v子树分配j这么大的空间
f[u][i] = max(f[u][i], f[v][j] + f[u][i - j]); // 给v分配j这么大的空间，剩余就是一个子问题了
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("NC19981.in", "r", stdin);
#endif
memset(h1, -1, sizeof h1); // 初始人链式前向星
memset(h2, -1, sizeof h2); // 初始人链式前向星
scanf("%d%d", &n, &m); // n个节点，m是最多能承受的重量上限
// 体积，价值
for (int i = 1; i <= n; i++) scanf("%d", W1 + i);
for (int i = 1; i <= n; i++) scanf("%d", V1 + i);
for (int i = 1; i <= n; i++) { // 枚举每个节点
int x; // i依赖于x,由x->i建边
scanf("%d", &x);
if (x) add(h1, x, i); // x为0表示当前节点不需要前序依赖
}
// Tarjan缩点
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
// 枚举每条出边
for (int u = 1; u <= n; u++)
for (int i = h1[u]; ~i; i = ne[i]) {
int v = e[i];
int a = id[u], b = id[v];
if (a != b) { // u和v不是同一个强连通分量，a-b之间创建边
add(h2, a, b);
in[b]++; // 标识强连通分量b的入度+1
}
}
// 枚举每个强连通分量，找出入度为零的强连通分量,从虚拟源点0向这个入度为零的强连通分量引一条边
for (int i = 1; i <= scc_cnt; i++)
if (!in[i]) add(h2, 0, i);
// 从超级源点出发，开始搜索
dfs(0);
// 从超级源点树的根0出发，分配容量最多为m时的最大价值
printf("%d\n", f[0][m]);
return 0;
}