标签：Tarjan重构图，树形DP
题目
题目描述
现在我们的手头有\(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\leq N\leq 100, 0\leq M\leq 500)\)
第2行：\(W_1,W_2, ... W_i, ..., W_n (0\leq W_i\leq M)\)
第3行：\(V_1, V_2, ..., V_i, ..., V_n (0\leq V_i\leq 1000)\)
第4行：\(D_1, D_2, ..., D_i, ..., D_n (0\leq D_i\leq N, D_i≠i)\)
输出格式
一个整数，代表最大价值
输入输出样例
输入样例#1
3 10
5 5 6
2 3 4
0 1 1
输出样例#1
5
分析
有先决条件的背包问题
考虑环的情况（要么选择整个环，要么整个舍弃）
首先用Tarjan把环的情况缩点重构图
然后跑一遍树形DP
设f[i][j]表示对i及其子树花费最多j的代价能够获得的最大价值
\[f[i][j]=max(f[i][j], f[i][k]+f[son][j-k])\]code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
const int maxn=1e3+6;
int n,m,cnt,scc,tim=0,top=0,v[maxn],w[maxn],last[maxn],last2[maxn];
int sv[maxn],sw[maxn],dfn[maxn],low[maxn],bel[maxn],que[maxn],f[maxn][maxn],in[maxn];
struct edge{int to,next;}e[maxn],e2[maxn];
bool inque[maxn];
void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;}
void insert2(int u,int v){in[v]=1;e2[++cnt]=(edge){v,last2[u]};last2[u]=cnt;}
void tarjan(int x){
int now=0;
low[x]=dfn[x]=++tim;que[++top]=x;inque[x]=1;
reg(x){
int v=e[i].to;
if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}
else if(inque[v])low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x]){
scc++;
while(now!=x){
now=que[top--];inque[now]=0;
bel[now]=scc;
sv[scc]+=v[now];
sw[scc]+=w[now];
}
}
}
void rebuild(){
cnt=0;
rep(x,1,n)
reg(x){
int v=e[i].to;
if(bel[v]!=bel[x])insert2(bel[x],bel[v]);
}
}
void dp(int x){
#define reg2(x) for(int i=last2[x];i;i=e2[i].next)
reg2(x){
int v=e2[i].to;
dp(v);
dep(j,m-sw[x],0)
rep(k,0,j)f[x][j]=max(f[x][j],f[x][k]+f[v][j-k]);
}
dep(j,m,0){
if(j>=sw[x])f[x][j]=f[x][j-sw[x]]+sv[x];
else f[x][j]=0;
}
}
int main()
{
n=read(),m=read();
rep(i,1,n)w[i]=read();
rep(i,1,n)v[i]=read();
rep(i,1,n){
int x=read();
if(x)insert(x,i);
}
rep(i,1,n)if(!dfn[i])tarjan(i);
rebuild();
rep(i,1,scc)
if(!in[i])insert2(scc+1,i);
dp(scc+1);
cout<<f[scc+1][m]<<endl;
return 0;
}
