首页 > itarticle > [haoi2010]软件安装

[haoi2010]软件安装

admin 11月 14, 2020 0

1.1【题目】

有n个软件，占用w[i]的空间，价值为v[i]，安装到一台磁盘容量为M的计算机上，使价值之和尽可能大。
有些软件之间存在依赖关系且一个软件最多依赖另一个软件。
软件i依赖软件d[i]，如果一个软件没有依赖，则d[i]=0

1.2【思路】

因为依赖关系有环的话，要不全选要不全不选所以要先缩点，重建图之后将所有树的根节点都连向0节点。
f [i][j]代表以i为根节点的子树，费用为j时所能获得的最大收益，具体递归从每个子节点向上走。

1.3【小结】

~~去年做的时候单纯以为是背包问题结果爆零~~

for(int i=1;i<=n;i++){
       val[c[i]]+=v[i];wei[c[i]]+=w[i];
       if(c[i]!=c[fa[i]]&&fa[i]){
           add_c(c[fa[i]],c[i]);vis[c[i]]++;
       }
   }
   for(int i=1;i<=cnt;i++){
       if(!vis[i]){
           add_c(cnt+1,i);
       }
   }
   dp(cnt+1);
   cout<<f[cnt+1][m]<<endl;