算法1
C++ 代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1050;
const int M = 2005;
int dfn[N], low[N], st[N], co[N], top = 0, tim = 0, col = 0;
int h[N], nxt[N], to[N], idx = 0;
int h1[N], nxt1[N], to1[N], idx1 = 0;
int f[N][N], W[N], V[N], n, m;
bool vis[N], G[N][N];
int cost[N], val[N], d[N];
int read(){
char c = getchar();
int f = 1, x = 0;
while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}
while(isdigit(c)){x = (x << 1) + (x << 3) + (c - '0'); c = getchar();}
return x * f;
}
void add(int u, int v){
to[++ idx] = v, nxt[idx] = h[u], h[u] = idx;
}
void add1(int u, int v){
to1[++ idx1] = v, nxt1[idx1] = h1[u], h1[u] = idx1;
}
void Tarjan(int u){
dfn[u] = low[u] = ++ tim;
st[++ top] = u;
vis[u] = 1;
for(int i = h[u]; i; i = nxt[i]){
int v = to[i];
if(!dfn[v]){
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]){
int v;
co[u] = ++ col;
vis[u] = 0;
while(v = st[top --], v != u) co[v] = col, vis[v] = 0;
}
}
void dp(int u){
int i, j;
for(i = cost[u];i <= m;i ++) f[u][i] = val[u];
for(int e = h1[u], v; e; e = nxt1[e]){
dp(v = to1[e]);
for(i = m - cost[u];i >= 0;i --)
for(j = 0;j <= i;j ++)
f[u][i + cost[u]] = max(f[u][i + cost[u]], f[u][i + cost[u] - j] + f[v][j]);
}
}
int main(){
int x;
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 ++) if(x = read()) add(x, i);
for(int i = 1;i <= n;i ++) if(!dfn[i]) Tarjan(i);
for(int i = 1;i <= n;i ++) {
cost[co[i]] += W[i];
val[co[i]] += V[i];
for(int j = h[i]; j; j = nxt[j])
if(co[i] != co[to[j]]) G[co[i]][co[to[j]]] = 1, d[co[to[j]]] ++;
}
for(int i = 1;i <= col;i ++)
for(int j = 1;j <= col;j ++)
if(G[i][j]) add1(i, j);
for(int i = 1;i <= col;i ++)
if(!d[i]) add1(col + 1, i);
printf("%d", (dp(col + 1), f[col + 1][m]));
return 0;
}