这题如果没有环的话就是一个依赖背包问题，可以树形DP
有环就用tarjan缩点就可以了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | #include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>using namespace std;int en,en2,h[105],h2[105],w[505],v[105],d[105],low[105],dfn[105],n,m,scc,dp[105][505],cnt,Q[105],Qcnt,inQ[105],belong[105],sv[105],sw[105],in[105];struct Edge{int b,next;}e[10005],e2[10005];void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}void AddEdge2(int sa,int sb){in[sb]=1;e2[++en2].b=sb;e2[en2].next=h2[sa];h2[sa]=en2;}void Tarjan(int u){dfn[u]=low[u]=++cnt;Q[++Qcnt]=u;inQ[u]=1;for(int i=h[u];i;i=e[i].next){ int v=e[i].b; if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);} else if(inQ[v]){low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]){ scc++; int nw=0; while(nw!=u){ nw=Q[Qcnt--];inQ[nw]=0; belong[nw]=scc; sv[scc]+=v[nw]; sw[scc]+=w[nw]; }}}void Rebuild(){for(int i=1;i<=n;i++){ for(int j=h[i];j;j=e[j].next){ int v=e[j].b; if(belong[i]!=belong[v]){ AddEdge2(belong[i],belong[v]); } }}for(int i=1;i<=scc;i++){if(!in[i])AddEdge2(scc+1,i);}}void DP(int u){for(int i=h2[u];i;i=e2[i].next){ int v=e2[i].b;DP(v); for(int j=m-sw[u];j>=0;j--){ for(int k=0;k<=j;k++){ dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][j-k]); } }}for(int j=m;j>=0;j--){ if(j>=sw[u])dp[u][j]=dp[u][j-sw[u]]+sv[u]; else dp[u][j]=0;}}int main(){freopen("2427.in","r",stdin);freopen("2427.out","w",stdout);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])AddEdge(d[i],i);}for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);Rebuild();DP(scc+1);printf("%d\n",dp[scc+1][m]);return 0;} |
评论 (0)
