2427: [HAOI2010]软件安装

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1987  Solved: 791

[ ][ ][ ]

Description

现在我们的手头有N个软件，对于一个软件i，它要占用W_i的磁盘空间，它的价值为V_i。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即V_i的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系：软件i依赖软件D_i。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则D_i=0，这时只要这个软件安装了，它就能正常工作。

Input

第1行：N, M  （0<=N<=100, 0<=M<=500）

      第2行：W₁, W₂, ... W_i, ..., W_n （0<=W_i<=M ）

      第3行：V₁, V₂, ..., V_i, ..., V_n  （0<=Vi<=1000 ）

      第4行：D₁, D₂, ..., D_i, ..., D_n（0<=D_i<=N, D_i≠i ）

Output

一个整数，代表最大价值。

Sample Input

3 10

5 5 6

2 3 4

0 1 1

Sample Output

5

HINT

Source

这么简单的题竟然做了三个小时？

环套树DP，为了方便直接Tarjan缩点然后跑树形DP即可。至于多叉树转二叉树这个方法完全不需要用上，直接做树上背包即可。

注意：除非卡常时，不要再用~i表示i>=0了，这样无法处理i<0的情况。

坚决避免低级错误！

1 #include
     
       2 #include
      
        3 #include
       
         4 #define rep(i,l,r) for (int i=l; i<=r; i++) 5 #define For(i,x) for (int i=h[x]; i; i=nxt[i]) 6 using namespace std; 7  8 const int N=2100; 9 int n,m,scc,cnt,tim,top,h[N<<1],ind[N],w[N],v[N],d[N],wei[N],val[N];10 int bel[N],dp[N][N],stk[N],inq[N],dfn[N],low[N],to[N<<2],nxt[N<<2];11 12 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }13 14 void tarjan(int x){15     low[x]=dfn[x]=++tim; inq[x]=1; stk[++top]=x;16     For(i,x){17         int k=to[i];18         if (!dfn[k]) tarjan(k),low[x]=min(low[x],low[k]);19             else if (inq[k]) low[x]=min(low[x],dfn[k]);20     }21     if (dfn[x]==low[x]){22         int t; scc++;23         do{ t=stk[top--]; inq[t]=0; bel[t]=scc; }while (t!=x);24     }25 }26 27 void dfs(int x){28     rep(i,wei[x],m) dp[x][i]=val[x];29     For(i,x){30         int k=to[i]; dfs(k);31         for (int j=m-wei[x]; j>=0; j--)32             rep(q,0,j)33                 dp[x][j+wei[x]]=max(dp[x][j+wei[x]],dp[x][j+wei[x]-q]+dp[k][q]);34     }35 }36 37 int main(){38     scanf("%d%d",&n,&m); scc=n;39     rep(i,1,n) scanf("%d",&w[i]);40     rep(i,1,n) scanf("%d",&v[i]);41     rep(i,1,n) { scanf("%d",&d[i]); if (d[i]) add(d[i],i); }42     rep(i,1,n) if (!dfn[i]) tarjan(i);43     rep(i,1,n){44         wei[bel[i]]+=w[i]; val[bel[i]]+=v[i];45         if (bel[i]!=bel[d[i]] && d[i]) add(bel[d[i]],bel[i]),ind[bel[i]]++;46     }47     rep(i,n+1,scc) if (!ind[i]) add(scc+1,i);48     dfs(scc+1); printf("%d\n",dp[scc+1][m]);49     return 0;50 }