题意：
有n个软件，每个大小为wi，价值为vi，同时每个软件依赖0个或一个其他软件，要求在大小不超过的m的前提下得到最大价值。n≤100，m≤500。
题解：
缩点然后做“树上背包dp”，具体看代码，注意里面用到了滚动数组。
代码：
1 #include2 #include 3 #include 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define dec(i,j,k) for(int i=j;i>=k;i--) 6 #define maxn 150 7 using namespace std; 8 9 int bel[maxn],scc,dfn[maxn],low[maxn],tim,st[maxn],top,sv[maxn],sw[maxn],v[maxn],w[maxn]; bool inst[maxn],ok[maxn];10 struct e1{ int f,t,n;}; e1 es1[maxn*5]; int g1[maxn],ess1;11 void pe1(int f,int t){es1[++ess1]=(e1){f,t,g1[f]}; g1[f]=ess1;}12 struct e2{ int t,n;}; e2 es2[maxn*10]; int g2[maxn],ess2;13 void pe2(int f,int t){es2[++ess2]=(e2){t,g2[f]}; g2[f]=ess2; ok[t]=1;}14 void init(){15 ess1=ess2=0; memset(g1,0,sizeof(g1)); memset(g2,0,sizeof(g2));16 tim=scc=0; memset(inst,0,sizeof(inst)); memset(dfn,0,sizeof(dfn));17 }18 void tarjan(int x){19 dfn[x]=low[x]=++tim; st[++top]=x; inst[x]=1;20 for(int i=g1[x];i;i=es1[i].n){21 if(!dfn[es1[i].t]){22 tarjan(es1[i].t); low[x]=min(low[x],low[es1[i].t]);23 }else if(inst[es1[i].t])low[x]=min(low[x],dfn[es1[i].t]);24 }25 if(dfn[x]==low[x]){26 scc++; int y=0; while(x!=y)y=st[top],bel[y]=scc,sv[scc]+=v[y],sw[scc]+=w[y],inst[y]=0,top--;27 }28 }29 void build(){inc(i,1,ess1)if(bel[es1[i].f]!=bel[es1[i].t])pe2(bel[es1[i].f],bel[es1[i].t]);}30 int f[maxn][maxn*5],n,m;31 void dfs(int x){32 for(int i=g2[x];i;i=es2[i].n){33 dfs(es2[i].t);34 dec(j,m-sw[x],0)inc(k,0,j)f[x][j]=max(f[x][j],f[x][k]+f[es2[i].t][j-k]);35 }36 dec(j,m,0)if(j>=sw[x])f[x][j]=f[x][j-sw[x]]+sv[x];else f[x][j]=0;37 }38 inline int read(){39 char ch=getchar(); int f=1,x=0;40 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar();}41 while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();42 return f*x;43 }44 int main(){45 n=read(); m=read(); inc(i,1,n)w[i]=read(); inc(i,1,n)v[i]=read(); init();46 inc(i,1,n){ int a=read(); if(a)pe1(a,i);} inc(i,1,n)if(!dfn[i])tarjan(i); build();47 inc(i,1,scc)if(!ok[i])pe2(scc+1,i); dfs(scc+1); printf("%d",f[scc+1][m]); return 0;48 }
20160614