【洛谷P2515】[HAOI2010]软件安装
题目描述
现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。
Tarjan+树形背包。
Tarjan就是为了恶心人的，注意建边。
模了第一篇题解大佬的奇淫技巧，对于fa是0的点，可以不去管它，等到缩完点重新建边之后，我们统计每个点的入度，如果该点入度为零，那么说明这个点是森林中一棵树的树根，那么这个时候我们再建立超级源点就可以了。
不然的话再所点之前建立超级源点真的恶心，深受其害。。。
至于树形DP，这道题和选课基本上一样，不过我发现了一种更好的有依赖的树形DP的写法，也算是现在才真正学会。
模板：
code：
void dfs(int u){
for(int i=w[u];i<=n;i++)f[u][i]=v[u];
for(int i=head[i];i;i=edge[i].nxt){
int v=edge[i].to;
dfs(v);
for(int j=m;j>=w[u];j--){
for(int k=0;k<=j-w[u];k++){
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
}
}
}
}
code:
#include <iostream>
#include <cstdio>
using namespace std;
const int wx=1017;
inline int read(){
int sum=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}
return sum*f;
}
int num1,num2,n,m,top,tot,col;
int head1[wx],head2[wx],dfn[wx],low[wx],st[wx];
int belong[wx],f[wx][wx],tmp[wx];
int w[wx],v[wx],W[wx],V[wx],fa[wx];
struct node{
int nxt,to;
}edge1[wx*2];
struct e{
int nxt,to;
}edge2[wx*2];
void add1(int from,int to){
edge1[++num1].nxt=head1[from];
edge1[num1].to=to;
head1[from]=num1;
}
void add2(int from,int to){
edge2[++num2].nxt=head2[from];
edge2[num2].to=to;
head2[from]=num2;
}
void Tarjan(int u){
dfn[u]=low[u]=++tot;
st[++top]=u;
for(int i=head1[u];i;i=edge1[i].nxt){
int v=edge1[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!belong[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
belong[u]=++col;
while(st[top]!=u){
belong[st[top]]=col;
top--;
}
top--;
}
}
void CQ(){
for(int i=1;i<=n;i++){
if(belong[i]!=belong[fa[i]]&&fa[i]){
add2(belong[fa[i]],belong[i]);
tmp[belong[i]]++;
}
}
for(int i=1;i<=n;i++){
W[belong[i]]+=w[i];
V[belong[i]]+=v[i];
}
for(int i=1;i<=col;i++){
if(!tmp[i])add2(col+1,i);
}
}
void dfs(int u){
for(int i=W[u];i<=m;i++)f[u][i]=V[u];
for(int i=head2[u];i;i=edge2[i].nxt){
int v=edge2[i].to;
dfs(v);
for(int j=m;j>=W[u];j--){
for(int k=0;k<=j-W[u];k++){
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
}
}
}
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++)w[i]=read();
for(int i=1;i<=n;i++)v[i]=read();
for(int i=1;i<=n;i++){
fa[i]=read();
if(!fa[i])continue;
add1(fa[i],i);
}
for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
CQ();
dfs(col+1);
printf("%d\n",f[col+1][m]);
return 0;
}