scy传统代码：

#include<bits/stdc++.h>
using namespace std;
const int N=110;
vector<int>G1[N],G2[N];
int n, m, tsp, cnt, nw[N], nv[N], sw[N], sv[N], d[N], dfn[N], low[N], rd[N], scc[N], f[N][510]; 
stack<int> sta; bool v[N];
void tarjan(int x)
{
    dfn[x]=low[x]=++id;
    sta.push(x); v[x]=1;
    for(int y:G1[x])
    {
        if(dfn[y]==0)
        {
            tarjan(y);
            low[x]=min(low[x], low[y]);
        }
        else if(v[y]) low[x]=min(low[x], dfn[y]);
    }
     
    if(dfn[x]==low[x])
    {
        cnt++;
        for(int z=0;z!=x;)
        {
            z=sta.top(); sta.pop(); v[z]=0; 
			scc[z]=cnt; 
            sw[cnt]+=nw[z]; sv[cnt]+=nv[z];
        }
    }
}
void dfs(int x)
{
	for(int i=sw[x];i<=m;i++)f[x][i]=sv[x];
    for(int y:G2[x])
    {
        dfs(y);
        for(int i=m; i>=sw[x]; i--)
            for(int j=0; j<=i-sw[x]; j++)
                f[x][i]=max(f[x][i], f[y][j]+f[x][i-j]);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &nw[i]);
    for(int i=1; i<=n; i++) scanf("%d", &nv[i]);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &d[i]);
        if(d[i]>0) G1[d[i]].push_back(i);
    }
    id=cnt=0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low));
    memset(scc, 0, sizeof(scc)); memset(v, 0, sizeof(v)); 
    memset(sv, 0, sizeof(sv));   memset(sw, 0, sizeof(sw));
    for(int i=1; i<=n; i++) if(dfn[i]==0) tarjan(i);
    
    memset(rd, 0, sizeof(rd));
    for(int i=1; i<=n; i++)
    {
        int x=scc[d[i]], y=scc[i];
        if(x!=y) {G2[x].push_back(y); rd[y]++;}
    }
    for(int i=1; i<=cnt; i++) if(rd[i]==0) G2[0].push_back(i);
    memset(f, 0, sizeof(f));
    dfs(0);
	printf("%d\n", f[0][m]);
    return 0;
}

scy巧妙的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=110;
vector<int>G1[N],G2[N],f[N];
int n, m, id, cnt, nw[N], nv[N], sw[N], sv[N], d[N], dfn[N], low[N], rd[N], scc[N]; 
stack<int> sta; bool v[N];
void tarjan(int x)
{
    dfn[x]=low[x]=++id;
    sta.push(x); v[x]=1;
    for(int y:G1[x])
    {
        if(dfn[y]==0)
        {
            tarjan(y);
            low[x]=min(low[x], low[y]);
        }
        else if(v[y]) low[x]=min(low[x], dfn[y]);
    }
     
    if(dfn[x]==low[x])
    {
        cnt++;
        for(int z=0;z!=x;)
        {
            z=sta.top(); sta.pop(); v[z]=0; 
			scc[z]=cnt; 
            sw[cnt]+=nw[z]; sv[cnt]+=nv[z];
        }
    }
}
int siz[N],rdfn[N],pool[110*510];
void dfs(int x)
{
    siz[x]=1;
    for(auto y:G2[x]) dfs(y),siz[x]+=siz[y];
    rdfn[++id]=x;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &nw[i]);
    for(int i=1; i<=n; i++) scanf("%d", &nv[i]);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &d[i]);
        if(d[i]>0) G1[d[i]].push_back(i);
    }
    id=cnt=0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low));
    memset(scc, 0, sizeof(scc)); memset(v, 0, sizeof(v)); 
    memset(sv, 0, sizeof(sv));   memset(sw, 0, sizeof(sw));
    for(int i=1; i<=n; i++) if(dfn[i]==0) tarjan(i);
    
    memset(rd, 0, sizeof(rd));
    for(int i=1; i<=n; i++)
    {
        int x=scc[d[i]], y=scc[i];
        if(x!=y) {G2[x].push_back(y); rd[y]++;}
    }
    for(int i=1; i<=cnt; i++) if(rd[i]==0) G2[0].push_back(i);
    int (&f)[n+2][m+1]=decltype(f)(pool);
    id=0;dfs(0);
    for(int i=1;i<=id;++i)
	{
        int x=rdfn[i];
        for(int j=0;j<=m;++j)
		{
            f[i][j]=f[i-siz[x]][j];
            if(j>=sw[x]) f[i][j]=max(f[i][j],f[i-1][j-sw[x]]+sv[x]);
        }
    }
	printf("%d\n", f[id][m]);
    return 0;
}

E96 Tarjan缩点+树上背包 P2515 [HAOI2010] 软件安装

// Tarjan缩点+树上背包 O(n*m)
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 505;
struct E
{
	int y, ne;
} e[N << 1];
int head[N], idx;
void add(int x, int y)
{
	e[++idx] = {y, head[x]};
	head[x] = idx;
}
int n, m, w[N], v[N], d[N];
int dfn[N], low[N], tim, scc[N], cnt, stk[N], top;
int W[N], V[N], ind[N], f[N][N];

void tarjan(int x)
{
	dfn[x] = low[x] = ++tim;
	stk[++top] = x;
	for (int i = head[x]; i; i = e[i].ne)
	{
		int y = e[i].y;
		if (!dfn[y])
		{ // 若y未访问
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (!scc[y]) // 若y已访问且未处理
			low[x] = min(low[x], dfn[y]);
	}
	if (dfn[x] == low[x])
	{
		++cnt;
		while (1)
		{
			int y = stk[top--];
			scc[y] = cnt;
			W[cnt] += w[y];
			V[cnt] += v[y];
			if (y == x)
				break;
		}
	}
}
void dfs(int x)
{
	for (int i = head[x]; i; i = e[i].ne)
	{
		int y = e[i].y;
		for (int j = 0; j <= m - W[y]; j++)
			f[y][j] = f[x][j] + V[y];
		dfs(y);
		for (int j = W[y]; j <= m; j++)
			f[x][j] = max(f[x][j], f[y][j - W[y]]);
	}
}
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++)
	{
		scanf("%d", &d[i]);
		if (d[i])
			add(d[i], i);
	}
	for (int i = 1; i <= n; i++) // 缩点
		if (!dfn[i])
			tarjan(i);
	for (int i = 1; i <= n; i++)
		head[i] = 0;
	idx = 0;
	for (int i = 1; i <= n; i++) // 连边
		if (scc[d[i]] != scc[i])
			add(scc[d[i]], scc[i]), ind[scc[i]]++;
	for (int i = 1; i <= cnt; i++) // 变成树
		if (!ind[i])
			add(0, i);
	dfs(0); // DP
	printf("%d\n", f[0][m]);
}