bzoj 2427 [HAOI2010]软件安装 Tarjan缩点+树形dp

[HAOI2010]软件安装

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2029 Solved: 811
[Submit][Status][Discuss]

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

HINT

树形，dp依赖型的，算完点，是一棵树对吧，然后就从根向下dp数据范围如此之小。f[i][j]表示i这个点，可以用安装连续几个点的方案数。

 #include<cstring>
 #include<cmath>
 #include<iostream>
 #include<algorithm>
 #include<cstdio> #define N 107
 #define M 507
 using namespace std;
 inline int read()
 {
     int x=,f=;char ch=getchar();
     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
     return x*f;
 } int n,m,cnt,scc,ind,top;
 int v[N],w[N];
 int sv[N],sw[N];
 int dfn[N],low[N],belong[N];
 int q[N],f[N][M],in[M];
 struct edge{
     int to,next;
 }e[M],ed[M];int last[N],last2[N];
 bool inq[N]; void insert(int u,int v){e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;}
 void insert2(int u,int v)
 {
     in[v]=;
     ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;
 }
 void tarjan(int x)
 {
     int now=;
     low[x]=dfn[x]=++ind;
     q[++top]=x;inq[x]=;
     for(int i=last[x];i;i=e[i].next)
         if(!dfn[e[i].to])
         {
             tarjan(e[i].to);
             low[x]=min(low[x],low[e[i].to]);
         }
         else if(inq[e[i].to])
             low[x]=min(low[x],dfn[e[i].to]);
     if(low[x]==dfn[x])
     {
         scc++;
         while(now!=x)
         {
             now=q[top--];inq[now]=;
             belong[now]=scc;
             sv[scc]+=v[now];
             sw[scc]+=w[now];
         }
     }
 }
 void rebuild()
 {
     cnt=;
     for(int x=;x<=n;x++)
         for(int i=last[x];i;i=e[i].next)
             if(belong[e[i].to]!=belong[x])
                 insert2(belong[x],belong[e[i].to]);
 }
 void dp(int x)
 {
     for(int i=last2[x];i;i=ed[i].next)
     {
         dp(ed[i].to);
         for(int j=m-sw[x];j>=;j--)
         {
             for(int k=;k<=j;k++)
                 f[x][j]=max(f[x][j],f[x][k]+f[ed[i].to][j-k]);
         }
     }
     for(int j=m;j>=;j--)
     {
         if(j>=sw[x])f[x][j]=f[x][j-sw[x]]+sv[x];
         else f[x][j]=;
     }
 }
 int main()
 {
     n=read();m=read();
     for(int i=;i<=n;i++) w[i]=read();
     for(int i=;i<=n;i++) v[i]=read();
     for(int i=;i<=n;i++)
     {
         int x=read();
         if(x)insert(x,i);
     }
     for(int i=;i<=n;i++)
         if(!dfn[i])tarjan(i);
     rebuild();
     for(int i=;i<=scc;i++)
         if(!in[i])
             insert2(scc+,i);
     dp(scc+);
     printf("%d\n",f[scc+][m]);
 }