题解 P2515 【[HAOI2010]软件安装】
xyz32768
2017-08-07 18:46:45
强连通分量+树形$DP$。
首先对于每个$i$，从$i$向$Di$建一条有向边。
在这里我们发现，依赖关系可以形成环。对于一个环，里面的节点要么都选，要么都不选。
所以，这里先$Tarjan$强连通分量缩点，构成一个新图，这样新图里的每个节点可以看成一个整体考虑（因为对应的原图里的节点要么都选要么都不选）。然后新建一个虚拟节点，向新图里所有的入度为$0$的节点建一条有向边，构成一棵树，以虚拟节点作为根。
建树完毕后，在构成的树上做$DP$。
以下$cost[i]$和$val[i]$分别为树上每个节点的费用和价值，设$f[u][i]$为在节点$u$的子树内，费用限制为$i$的条件下能取到的最大价值，此时对于每个$u$，首先把$f[u][i]$（$cost[u]<=i<=m$）设为$val[u]$。
然后如果第一层循环$u$的子节点$v$，第二层**倒序**循环$i$（从$m-cost[u]$到$0$），第三层**顺序**循环节点$v$的子树的费用限制$j$（从$0$到$i$），则转移方程为：$f[u][i+cost[u]]=max(f[u][i+cost[u]],f[u][i+cost[u]-j]+f[v][j])$。
最后答案为$f[虚拟节点][m]$。
代码：
```cpp
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
int res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
return bo ? ~res + 1 : res;
}
const int N = 105, M = 505;
int n, m, W[N], V[N], f[N][M], ecnt, nxt[M], adj[N], go[M], top,
sta[N], dfn[N], low[N], times, num, bel[N], cost[N], val[N], ecnt2,
nxt2[M], adj2[N], go2[M], d[N];
bool ins[N], G[N][N];
void add_edge(int u, int v) {
nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
}
void add_edge2(int u, int v) {
nxt2[++ecnt2] = adj2[u]; adj2[u] = ecnt2; go2[ecnt2] = v;
}
void Tarjan(int u) {
dfn[u] = low[u] = ++times;
sta[++top] = u; ins[u] = 1;
for (int e = adj[u], v; e; e = nxt[e])
if (!dfn[v = go[e]]) {
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]) {
int v; bel[u] = ++num; ins[u] = 0;
while (v = sta[top--], v != u) bel[v] = num, ins[v] = 0;
}
}
void dp(int u) {
int i, j;
for (i = cost[u]; i <= m; i++) f[u][i] = val[u];
for (int e = adj2[u], v; e; e = nxt2[e]) {
dp(v = go2[e]);
for (i = m - cost[u]; i >= 0; i--) for (j = 0; j <= i; j++)
f[u][i + cost[u]] = max(f[u][i + cost[u]],
f[u][i + cost[u] - j] + f[v][j]);
}
}
int main() {
int i, j, x; n = read(); m = read();
for (i = 1; i <= n; i++) W[i] = read();
for (i = 1; i <= n; i++) V[i] = read();
for (i = 1; i <= n; i++) if (x = read()) add_edge(x, i);
for (i = 1; i <= n; i++) if (!dfn[i]) Tarjan(i);
for (i = 1; i <= n; i++) {
cost[bel[i]] += W[i]; val[bel[i]] += V[i];
for (int e = adj[i]; e; e = nxt[e])
if (bel[i] != bel[go[e]]) G[bel[i]][bel[go[e]]] = 1,
d[bel[go[e]]]++;
}
for (i = 1; i <= num; i++) for (j = 1; j <= num; j++)
if (G[i][j]) add_edge2(i, j);
for (i = 1; i <= num; i++) if (!d[i])
add_edge2(num + 1, i);
printf("%d\n", (dp(num + 1), f[num + 1][m]));
return 0;
}
```