题目描述

Description

现在我们的手头有N个软件，对于一个软件i，它要占用W_i的磁盘空间，它的价值为V_i。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即V_i的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系：软件i依赖软件D_i。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则D_i=0，这时只要这个软件安装了，它就能正常工作。

Input

第1行：N, M  （0<=N<=100, 0<=M<=500）
第2行：W₁, W₂, … W_i, …, W_n （0<=W_i<=M ）
第3行：V₁, V₂, …, V_i, …, V_n  （0<=Vi<=1000 ）
第4行：D₁, D₂, …, D_i, …, D_n （0<=D_i<=N, D_i≠i ）

Output

一个整数，代表最大价值。

Sample Input

3 10
5 5 6
2 3 4
0 1 1

Sample Output

5

题目分析：

给出了一个有树和环的树 因为如果有环肯定是整个环都选对答案才能有贡献 那么我们将环用tarjan缩点 用一个虚点将所有入度为0的点连接，然后跑一遍树上背包

树上背包不会QAQ 只好看了hzwer的题解 呐 不多说了 刷树形DP去！

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int deep[200],low[200],belong[200];
bool vis[200];
int dis[200];
int heada[200];
int headb[200];
int ww[200],vv[200];
int w[200],v[200];
int in[200];
int tot_a,tot_b,color,time;
struct your
{
    int to,next;
}a[1010],b[1010];
void add_a(int x,int y)
{
    a[++tot_a].next=heada[x];
    a[tot_a].to=y;
    heada[x]=tot_a;
}
void add_b(int x,int y)
{
    b[++tot_b].next=headb[x];
    b[tot_b].to=y;
    headb[x]=tot_b;
}
void tarjan(int x)
{
    deep[x]=low[x]=++time;
    dis[++dis[0]]=x;
    vis[x]=true;
    for(int i=heada[x];i;i=a[i].next)
    {
        if(!deep[a[i].to])
        {
            tarjan(a[i].to);
            low[x]=min(low[x],low[a[i].to]);
        }
        else if(vis[a[i].to])
            low[x]=min(low[x],deep[a[i].to]);
    }
    if(deep[x]==low[x])
    {
        int tmp;
        color++;
        do
        {
            tmp=dis[dis[0]--];
            belong[tmp]=color;
            vis[tmp]=false;
            vv[color]+=v[tmp];
            ww[color]+=w[tmp];
        }while(tmp!=x);
    }
}
int f[105][505];
void dfs(int x,int temp)
{
    for(int i=headb[x];i;i=b[i].next)
    {
        if(b[i].to==temp) continue;
        dfs(b[i].to,x);
        for(int j=m-ww[x];j>=0;j--)
            for(int k=0;k<=j;k++)
                f[x][j]=max(f[x][j],f[b[i].to][j-k]+f[x][k]);
    }
    for(int i=m;i>=0;i--)
        if(i>=ww[x]) f[x][i]=f[x][i-ww[x]]+vv[x];
        else f[x][i]=0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        if(tmp) add_a(tmp,i);
    }
    for(int i=1;i<=n;i++)
        if(!deep[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=heada[i];j;j=a[j].next)
            if(belong[i]!=belong[a[j].to])
                add_b(belong[i],belong[a[j].to]),in[belong[a[j].to]]++;
    for(int i=1;i<=color;i++)
        if(!in[i]) add_b(color+1,i);
    dfs(color+1,0);
    printf("%d",f[color+1][m]);
    return 0;
}