简单的tarjan+（本蒟蒻刚刚接触不久）恶心的树形DP

题面

题目描述
现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。
输入输出格式
输入格式：
第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 ）
输出格式：
一个整数，代表最大价值
输入输出样例
输入样例#1：
3 10
5 5 6
2 3 4
0 1 1
输出样例#1：
5

解题思路

有可能出现依赖关系的环，我们把环tarjan缩成点，因为你选择这个环中的任意一个软件都需要把这个环整个都安装，所以直接累加这个环的w和v缩点。

暴力重新建图后，整个就形成了一个森林，为了方便，建一个虚的树根连上每个入度为0的点，然后在树上跑DP求解。

DP：设f[i][j]表示i节点容量为j所得的最大价值，由它的儿子转移过来

空间，常数巨大的代码

# include <stdio.h>

# include <stdlib.h>

# include <iostream>

# include <string.h>

using namespace std;

# define N 501

# define IL inline

# define RG register

# define UN unsigned

# define ll long long

# define oo 2147483647

# define mem(a, b) memset(a, b, sizeof(a))

# define max(a, b) ((a) > (b)) ? (a) : (b)

# define min(a, b) ((a) < (b)) ? (a) : (b)

IL int Get(){

    RG char c = '!'; RG int num = 0, z = 1;

    while(c != '-' && (c > '9' || c < '0')) c = getchar();

    if(c == '-') z = -1, c = getchar();

    while(c >= '0' && c <= '9') num = num * 10 + c - '0', c = getchar();

    return num * z;

}

int n, w[N], m, v[N], ft[N], to[N], nt[N], cnt, f[N][501];

int dfn[N], low[N], bg[N], isk[N], sk[N], cnt1, num, r[N];

IL void Add(RG int u, RG int vv){

    nt[cnt] = ft[u]; to[cnt] = vv; ft[u] = cnt++;

}

IL void Dfs(RG int u){

    dfn[u] = low[u] = ++cnt1;

    isk[u] = 1; sk[++sk[0]] = u;

    for(RG int e = ft[u]; e != -1; e = nt[e]){

        RG int vv = to[e];

        if(!dfn[vv]){

            Dfs(vv);

            low[u] = min(low[u], low[vv]);

        }

        else if(isk[vv]) low[u] = min(low[u], dfn[vv]);

    }

    if(dfn[u] == low[u]){

        RG int vv = sk[sk[0]--]; isk[vv] = 0;

        bg[vv] = ++num; w[num] += w[vv]; v[num] += v[vv];

        while(u != vv){

            vv = sk[sk[0]--];

            isk[vv] = 0;

            bg[vv] = num; w[num] += w[vv]; v[num] += v[vv];

        }

    }

}

IL void DP(RG int u){

    for(RG int j = m; j >= w[u]; j--)

        f[u][j] = v[u];

    for(RG int e = ft[u]; e != -1; e = nt[e]){

        RG int vv = to[e];

        DP(to[e]);

        for(RG int j = m - w[u]; j >= 0; j--)

            for(RG int k = 0; k <= j; k++)

                f[u][j + w[u]] = max(f[u][j + w[u]], f[u][j + w[u] - k] + f[vv][k]);

    }

}

int main(){

    mem(ft, -1);

    n = Get(); m = Get();

    for(RG int i = 1; i <= n; i++)

        w[i] = Get();

    for(RG int i = 1; i <= n; i++)

        v[i] = Get();

    for(RG int i = 1; i <= n; i++){

        RG int u = Get();

        if(u) Add(u, i);

    }

    num = n;

    for(RG int i = 1; i <= n; i++)

        if(!dfn[i]) Dfs(i);

    for(RG int i = 1; i <= n; i++)

        for(RG int e = ft[i]; e != -1; e = nt[e]){

            RG int vv = to[e];

            if(bg[i] != bg[vv]) Add(bg[i], bg[vv]), r[bg[vv]]++;

        }

    for(RG int i = n + 1; i <= num; i++)

        if(!r[i]) Add(num + 1, i);

    DP(num + 1);

    printf("%d\n", f[num + 1][m]);

    return 0;

}

我不会告诉你，这道题我写萎了交了n遍才A