洛谷2515 [HAOI2010]软件安装

标签：Tarjan重构图，树形DP

题目

题目传送门

题目描述

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

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

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

输入输出格式

输入格式

第1行：$N,M(0\le N\le 100,0\le M\le 500)$

第2行：$W_1,W_2,...W_i,...,W_n(0\le W_i\le M)$

第3行：$V_1,V_2,...,V_i,...,V_n(0\le V_i\le 1000)$

第4行：$D_1,D_2,...,D_i,...,D_n(0\le D_i\le N,D_i?=i)$

输出格式

一个整数，代表最大价值

输入输出样例

输入样例#1

3 10
5 5 6
2 3 4
0 1 1

输出样例#1

5

分析

有先决条件的背包问题

考虑环的情况（要么选择整个环，要么整个舍弃）

首先用Tarjan把环的情况缩点重构图

然后跑一遍树形DP

设f[i][j]表示对i及其子树花费最多j的代价能够获得的最大价值

$f[i][j]=max(f[i][j],f[i][k]+f[son][j?k])$

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
    ll f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
//**********head by yjjr**********
const int maxn=1e3+6;
int n,m,cnt,scc,tim=0,top=0,v[maxn],w[maxn],last[maxn],last2[maxn];
int sv[maxn],sw[maxn],dfn[maxn],low[maxn],bel[maxn],que[maxn],f[maxn][maxn],in[maxn];
struct edge{
    int to,next;}e[maxn],e2[maxn];
bool inque[maxn];
void insert(int u,int v){
    e[++cnt]=(edge){
    v,last[u]};last[u]=cnt;}
void insert2(int u,int v){
    in[v]=1;e2[++cnt]=(edge){
    v,last2[u]};last2[u]=cnt;}
void tarjan(int x){
    int now=0;low[x]=dfn[x]=++tim;que[++top]=x;inque[x]=1;reg(x){
    int v=e[i].to;if(!dfn[v]){
    tarjan(v);low[x]=min(low[x],low[v]);}else if(inque[v])low[x]=min(low[x],dfn[v]);}if(low[x]==dfn[x]){
    scc++;while(now!=x){
    now=que[top--];inque[now]=0;bel[now]=scc;sv[scc]+=v[now];sw[scc]+=w[now];}}
}
void rebuild(){
    cnt=0;rep(x,1,n)reg(x){
    int v=e[i].to;if(bel[v]!=bel[x])insert2(bel[x],bel[v]);}
}
void dp(int x){
    
#define reg2(x) for(int i=last2[x];i;i=e2[i].next) reg2(x){
    int v=e2[i].to;dp(v);dep(j,m-sw[x],0)rep(k,0,j)f[x][j]=max(f[x][j],f[x][k]+f[v][j-k]);}dep(j,m,0){
    if(j>=sw[x])f[x][j]=f[x][j-sw[x]]+sv[x];else f[x][j]=0;}
}
int main()
{
    n=read(),m=read();rep(i,1,n)w[i]=read();rep(i,1,n)v[i]=read();rep(i,1,n){
    int x=read();if(x)insert(x,i);}rep(i,1,n)if(!dfn[i])tarjan(i);rebuild();rep(i,1,scc)if(!in[i])insert2(scc+1,i);dp(scc+1);cout<<f[scc+1][m]<<endl;return 0;
}