洛谷 P2515 [HAOI2010]软件安装
Description
现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。
Input
第1行：N, M （0<=N<=100, 0<=M<=500）
第2行：W1, W2, ... Wi, ..., Wn （0<=Wi<=M ）
第3行：V1, V2, ..., Vi, ..., Vn （0<=Vi<=1000 ）
第4行：D1, D2, ..., Di, ..., Dn （0<=Di<=N, Di≠i ）
Output
- 一个整数，代表最大价值
Sample Input
3 10
5 5 6 2 3 4 0 1 1
Sample Output
5
题解：
- tarjan缩点 + 树形dp。
- 挺简单的，
要不是把边建反了可以一A - 首先如果有一个强连通分量，那么这里头的软件要不全部安装，要不全部不安装。安装一些肯定是不优的（花了钱却拿不到货）。所以第一步先跑一遍缩点。
- 缩点之后就开始跑树形dp。流程如下：
- 初始化当前点x的dp值。即dp(x, w[x] ~ m) = v[x]
- (i)：枚举x的所有儿子
- (j)：（用01背包的思路）枚举买了x后剩下可用的花费（即从m - w[x] ~ w[son]）
- (k)：枚举给当前儿子用多少花费（即从w[son] ~ m - w[x]）
- dp(x, j + b[x].w) = max(dp(x, j + b[x].w), dp(x, j + b[x].w - k) + dp(now, k) （now为上文的son）
- 这是我yy的，写完后发现，
这不就是树形dp标算吗？？
#include#include #include #include #define N 5005#define M 5005using namespace std;stack stk;struct E {int next, to;} e[N];struct B {int w, v;} b[N];struct A {int w, v;} a[N];int n, m, num, dex, tot;int h[N], low[N], dfn[N];int v[N], bel[N], in[N];int dp[N][M];bool vis[N];void add(int u, int v){ e[++num].next = h[u]; e[num].to = v; h[u] = num;}void tarjan(int x){ low[x] = dfn[x] = ++dex; vis[x] = 1, stk.push(x); for(int i = h[x]; i != 0; i = e[i].next) if(!dfn[e[i].to]) { tarjan(e[i].to); low[x] = min(low[x], low[e[i].to]); } else if(vis[e[i].to]) low[x] = min(low[x], dfn[e[i].to]); if(low[x] == dfn[x]) { tot++; while(1) { int now = stk.top(); vis[now] = 0, stk.pop(); b[tot].w += a[now].w; b[tot].v += a[now].v; bel[now] = tot; if(now == x) break; } }}void dfs(int x){ vis[x] = 1; for(int i = h[x]; i != 0; i = e[i].next) if(!vis[e[i].to]) dfs(e[i].to); for(int i = b[x].w; i <= m; i++) dp[x][i] = b[x].v; for(int i = h[x]; i != 0; i = e[i].next) { int now = e[i].to; for(int j = m - b[x].w; j >= b[now].w; j--) for(int k = b[now].w; k <= j; k++) dp[x][j + b[x].w] = max(dp[x][j + b[x].w], dp[x][j + b[x].w - k] + dp[now][k]); }}int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) cin >> a[i].w; for(int i = 1; i <= n; i++) cin >> a[i].v; for(int i = 1; i <= n; i++) { cin >> v[i]; if(!v[i]) continue; add(v[i], i); } for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); num = 0; memset(h, 0, sizeof(h)); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) if(!v[i]) continue; else if(bel[v[i]] != bel[i]) { add(bel[v[i]], bel[i]); in[bel[i]]++; } bel[++tot] = tot; for(int i = 1; i < tot; i++) if(!in[i]) add(tot, i); dfs(tot); cout << dp[tot][m]; return 0;}