这道题比较显然地,是一道树形背包;
但是会有环,怎么办呢?
缩点!tarjan缩点!
然后在新图上跑树形背包就可以AC了
#include <bits/stdc++.h> #define inc(i,a,b) for(register int i=a;i<=b;i++) using namespace std; int head[1010],cnt,head2[1010],cnt2; class littlestar{ public: int to,nxt; void add(int u,int v){ to=v;nxt=head[u]; head[u]=cnt; } void add2(int u,int v){ to=v;nxt=head2[u]; head2[u]=cnt2; } }star[20010],star2[20010]; int n,m; int a[210],b[210]; int tmp[210]; int low[210],dfn[210],st[210],top; int cur,co[210],col; void tarjan(int u) { low[u]=dfn[u]=++cur; st[++top]=u; for(int i=head[u];i;i=star[i].nxt){ int v=star[i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(!co[v]){ low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ co[u]=++col; while(st[top]!=u){ co[st[top]]=col; --top; } --top; } } int S; int f[110][1100]; int cost[210],val[210]; void dfs(int u,int fa) { for(int j=m;j>=cost[u];j--){ f[u][j]=max(f[u][j],f[u][j-cost[u]]+val[u]); } for(int i=head2[u];i;i=star2[i].nxt){ int v=star2[i].to; if(v==fa) continue; dfs(v,u); for(int j=m;j>=0;j--){ for(int k=j-cost[u];k>=0;k--){ f[u][j]=max(f[u][j],f[v][k]+f[u][j-k]); } } } } int father[110],rudu[110]; int main() { scanf("%d%d",&n,&m); S=n+1; inc(i,1,n) scanf("%d",&a[i]); inc(i,1,n) scanf("%d",&b[i]); inc(i,1,n){ int pre; scanf("%d",&pre); father[i]=pre; if(pre==0) tmp[++tmp[0]]=i; else{ star[++cnt].add(pre,i); } } inc(i,1,n){ if(!dfn[i]) tarjan(i); } inc(i,1,n){ cost[co[i]]+=a[i]; val[co[i]]+=b[i]; } inc(i,1,n){ if(father[i]!=0&&co[father[i]]!=co[i]){ star2[++cnt2].add2(co[father[i]],co[i]); rudu[co[i]]++; } } inc(i,1,col){ if(rudu[i]==0){ star2[++cnt2].add2(S,i); } } dfs(S,0); int ans=0; inc(i,0,m){ ans=max(ans,f[S][i]); } cout<<ans; } /* */