Tarjan板子和自己以前打的对比过,似乎没问题?
有dalao帮忙康康吗/kel
#include<cstdio>
const int M=105;
int n,m,dfc,BCC,top,bl[M],num[M],stk[M],dfn[M],low[M];bool ist[M];
int w[M],v[M],W[M],V[M],dp[M][505];
struct Edge{
int to;
Edge*nx;
}g[M<<1],e[M],*h[M],*k[M],*cnt=e;
inline int min(const int&a,const int &b){
return a>b?b:a;
}
inline int max(const int&a,const int&b){
return a>b?a:b;
}
inline void Add(int u,int v,Edge**h=k){
*cnt=(Edge){v,h[u]};h[u]=cnt++;
}
void Tarjan(int u){
low[u]=dfn[u]=++dfc;
ist[stk[++top]=u]=true;
for(Edge*E=h[u];E;E=E->nx){
int v=E->to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ist[v])low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
int t;
++BCC;
do{
ist[t=stk[top--]]=false;
bl[t]=BCC;
w[bl[t]]+=W[t];
v[bl[t]]+=V[t];
}while(t!=u);
}
}
inline void DP(int u,int v){
int i,j;
for(i=m;~i;--i){
for(j=i;~j;--j){
dp[u][i]=max(dp[u][i],dp[u][j]+dp[v][i-j]);
}
}
}
void DFS(int u,int f){
ist[u]=true;
for(Edge*E=k[u];E;E=E->nx){
int v=E->to;
if(v==f)continue;
DFS(v,u);
DP(u,v);
}
for(int i=m;i>=w[u];--i)dp[u][i]=max(dp[u][i],dp[u][i-w[u]]+v[u]);
}
signed main(){
int i,j,x;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)scanf("%d",W+i);
for(i=1;i<=n;++i)scanf("%d",V+i);
for(i=1;i<=n;++i){
scanf("%d",&x);
if(x)Add(x,i,h);
}
for(i=1;i<=n;++i)if(!dfn[i])Tarjan(i);
cnt=g;
for(i=1;i<=n;++i){
for(Edge*E=h[i];E;E=E->nx)if(bl[E->to]!=bl[i]){
Add(bl[E->to],bl[i]);++num[bl[E->to]];
Add(bl[i],bl[E->to]);++num[bl[i]];
}
}
for(x=1;x<=BCC;++x)if((num[x]==1||!num[x])&&!ist[x]){
DFS(x,0);
DP(0,x);
}
printf("%d",dp[0][m]);
}