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]);

 }

秒客网