软件安装
内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目描述
输入格式
输出格式
样例
没什么好说的。
非常简单的树dp
10分算法
其实是你dp打错了才会10分。
1个注意点(由于博主沙雕打法导致的)
if(x!=0) { for(ll j=m;j>=w1[x];j--) f[x][j]=f[x][j-w1[x]]+v1[x]; for(ll j=w1[x]-1;j;j--) f[x][j]=0; }
没清零!(上面给它赋值了但实施上它本来就不该有值)
40分算法
没打tarjan就会40分。
事实上当你发现你一直40wrong ans并且改不出来时就应该想想tarjan
100分
如果打了tarjan就100分了。
和某个叫「选课」的题特别像。
选课会打这个就会。
以下是本人丑陋的代码。
#include<bits/stdc++.h> #define ll long long #define A 2100 using namespace std; ll ver[A],f[A][A],fa[A],dis[A],deep[A],chatot=0,root,sum[A],w[A],d[A],v[A],num=0,top=0,ins[A],sta[A],dfn[A],low[A],cnt=0,scc[110][110],belong[A]; ll head2[A],head[A],nxt[A],nxt2[A],ver2[A],tot2=0,tot=0,du[A],v1[A],w1[A]; bool flag[A],vis[A]; ll n,m,k,t,xx,yy,zz; inline ll read(){ll f=1,x=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;} inline void add(ll x,ll y){fa[y]=x,ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;} inline void add2(ll x,ll y){ver2[++tot2]=y,nxt2[tot2]=head2[x],head2[x]=tot2;} inline void rebuilt() { for(ll i=1;i<=n;i++) { for(ll j=head[i];j;j=nxt[j]) { ll y=ver[j]; if(belong[y]!=belong[i]) add2(belong[i],belong[y]),du[belong[y]]++; } } } inline ll tarjan(ll x) { dfn[x]=low[x]=++num; sta[++top]=x;ins[x]=1; for(ll i=head[x];i;i=nxt[i]) { ll y=ver[i]; if(dfn[y]==0) { tarjan(y); low[x]=min(low[x],low[y]); } else if(ins[y]) low[x]=min(low[x],dfn[y]); } if(dfn[x]==low[x]) { ++cnt; ll yy=0; while(1) { yy=sta[top--]; ins[yy]=0; belong[yy]=cnt; v1[cnt]+=v[yy]; w1[cnt]+=w[yy]; if(yy==x) break; } } } void dfs(ll x) { f[x][0]=0; for(ll i=head2[x];i;i=nxt2[i]) { ll y=ver2[i]; dfs(y); for(ll j=m;j>=0;j--) for(ll k=j;k>=0;k--) f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]); } if(x!=0) { for(ll j=m;j>=w1[x];j--) f[x][j]=f[x][j-w1[x]]+v1[x]; for(ll j=w1[x]-1;j;j--) f[x][j]=0; } } int main() { n=read(),m=read(); for(ll i=1;i<=n;i++) w[i]=read(); for(ll i=1;i<=n;i++) v[i]=read(); for(ll i=1;i<=n;i++) { d[i]=read(); add(d[i],i); } for(ll i=1;i<=n;i++) if(!dfn[i]) tarjan(i); rebuilt(); for(ll i=1;i<=cnt;i++) { if(!du[i]) add2(0,i); } dfs(0); cout<<f[0][m]<<endl; }