题解：软件安装

题目https://www.luogu.com.cn/problem/P2515注意软件的依赖关系可能形成一个环a依赖bb依赖cc依赖a如果想要让环上的一个软件起作用必须得下载环上的所有软件。所以需要先缩点。缩点完成后重新建图该题就是经典的树形依赖背包问题。定义dp[i][j]为以i为根的子树在选择了i的前提下背包容量为j时的最大价值。dp过程中外层循环枚举背包容量内层循环枚举分配给当前子树的背包容量然后对于父节点u当前背包容量为j和子节点v以及分配给子树的背包容量为k那么dp[u][j]max(dp[u][j],dp[u][j-k]dp[v][k])父节点和遍历到v之前的其他子树用j-k容量的最大价值加上子树v用k容量产生的最大价值。因为要提前知道子节点的情况所以进行递归从下往上更新。考虑到可能会有多棵树所以创建一个虚拟节点0连接每棵树的根节点。那么dp完后的答案就是dp[0][m]dp部分voiddfs(intu){if(cost[u]m)//父节点的容量已经超过整个背包容量,直接放弃这棵子树return;dp[u][cost[u]]val[u];//先选择父节点(这棵子树的根节点)for(intv:ad[u]){dfs(v);//递归收集子树的情况for(intjm;jcost[u];j--)//倒着枚举背包容量,保证只选择该子树一次{for(inti0;ij-cost[u];i)//枚举可以分配给这棵子树的容量{dp[u][j]max(dp[u][j],dp[u][j-i]dp[v][i]);}}}}软件多次安装价值不会叠加所以是01背包问题。外层循环需要倒着枚举因为dp[u][j]的更新需要依赖dp表同层且列数更小的dp[u][j-i]需要保证dp[u]这一层j列前的数据是上一次产生的数据。如果正着遍历的话dp[u][j-i]可能已经被j-i列前面以及子树v的数据更新过这代表已经选择了子树v一次如果用这个数据去更新dp[u][j]的话会导致v又被选择一次。可能出现的情况正着遍历是先1后2j-i位置已经算入了子树v的价值到位置j时依赖j-i位置和子树v进行更新v会再次被算入。总之正序遍历会导致v的贡献被累加多次需要保证j前面的数据还没有被更新过所以需要倒着进行更新。总代码//缩点建图统计入边复杂度为O(n),去重为O(nlogn),每条树边进行一次dp,dp过程为O(n*m^2)//前两项过小忽略,整体复杂度为O(n*m^2)#includebits/stdc.husingnamespacestd;#defineintlonglong#defineinf1e18constintN105;constintM505;intc[N],v[N],in[N];//c:软件容量 v:软件价值 in:入度intdfn[N],low[N],stk[N];intscc[N],ins[N],cost[N],val[N];//scc:每个点所在的强连通分量编号//cost:强连通分量的容量 val:强连通分量的价值intdp[N][M];//dp[i][j] 以i为根的子树,选择i的前提下背包容量为j的最大价值vectorintadj[N],ad[N];intn,m,ti,tp,id;voidtarjan(intu){dfn[u]low[u]ti;stk[tp]u;ins[u]1;for(intv:adj[u]){if(!dfn[v]){tarjan(v);low[u]min(low[u],low[v]);}elseif(ins[v]){low[u]min(low[u],dfn[v]);}}if(low[u]dfn[u]){id;do{intxstk[tp];scc[x]id;ins[x]0;cost[id]c[x];val[id]v[x];}while(stk[tp--]!u);}}voiddfs(intu){if(cost[u]m)//父节点的容量已经超过整个背包容量,直接放弃这棵子树return;dp[u][cost[u]]val[u];//先选择父节点(这棵子树的根节点)for(intv:ad[u]){dfs(v);//递归收集子树的情况for(intjm;jcost[u];j--)//倒着枚举背包容量,保证只选择该子树一次{for(inti0;ij-cost[u];i)//枚举可以分配给这棵子树的容量{dp[u][j]max(dp[u][j],dp[u][j-i]dp[v][i]);}}}}voidsolve(){cinnm;for(inti1;in;i)cinc[i];for(inti1;in;i)cinv[i];for(inti1;in;i){intx;cinx;if(x0)continue;adj[x].push_back(i);}for(inti1;in;i){if(!dfn[i])tarjan(i);}for(intu1;un;u){intascc[u];for(intv:adj[u]){intbscc[v];if(ab)continue;ad[a].push_back(b);in[b];}}for(inti1;iid;i){if(in[i]0){ad[0].push_back(i);}}for(inti1;iid;i){sort(ad[i].begin(),ad[i].end());ad[i].erase(unique(ad[i].begin(),ad[i].end()),ad[i].end());}dfs(0);coutdp[0][m]endl;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT1;// cin T;while(T--){solve();}return0;}