[解题记录] [HAOI2010]软件安装

P2515 [HAOI2010]软件安装

题意简述

现在我们的手头有 \(N\) 个软件，对于一个软件\(i\) ，它要占用 \(W_i\) 的磁盘空间，它的价值为 \(V_i\) ，我们希望从中选择

一些软件安装到一台磁盘容量为 \(M\) 计算机上，使得这些软件的价值尽可能大（即 \(V_i\) 的和最大），软件之间存

在=依赖关系，即软件 \(i\) 只有在安装了软件\(j\) （包括软件 \(j\) 的直接或间接依赖）的情况下才能正确工作（软件 \(i\) 依

赖软件 \(j\) )，幸运的是，一个软件最多依赖另外一个软件

解题思路

可以把软件之间的依赖关系看成一条有向边，只有选择了祖先才能选择孙子结点，这样就可以直接跑树上背包了

但是题目中可能会有环的情况，这个时候就要用 \(tarjan\) 先缩点了，根据题目中的描述可以知道，在环上的点，

要么都选，要么都不选，所以缩点后把环内所有的点的价值的重量都累积起来就行了

但是即便如此，我们依旧无法保证图是一棵树，它有可能是一个森林，所以我们需要建一个虚点，并将它把所有

入度为 \(0\) 的点相连，它的价值和重量都设为 \(0\)

然后就可以开始DP了，设 \(f_{u,i}\) 表示在 \(u\) 这个点，花费 \(i\) 的限制，能获得的最大价值，因为软件之间的依赖关系

所以初始化为 \(f_{u,i}=v_u,i\in [w_u,m]\)，分别枚举 \(i∈[0,m?w_u]\) 表示对所有子树的限制，\(j∈[0,i]\) 表示对当

前子树的限制

code
#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
map mp;
const int N=2e5+10;
int cut[N],head[N],ver[N],nxt[N],dfn[N],low[N],dfstime,n,m,c[N],ins[N],vis[N],top,tot,sta[N],cnt,num,sd[N],nxt1[N],head1[N],ver1[N],tot1,was[N],val[N],V[N],f[N],d[N],w[N],in[N],ans,a[N],dp[3000][3000];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
inline void add1(int x,int y){
    ver1[++tot1]=y,nxt1[tot1]=head1[x],head1[x]=tot1;
}
inline void add(int x,int y){
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot,in[y]++;
}
void tarjan(int u){
    dfn[u]=low[u]=++dfstime;
    sta[++top]=u,ins[u]=1;
    for(int i=head1[u];i;i=nxt1[i]){
	int v=ver1[i];
	if(!dfn[v]){
	    tarjan(v);
	    low[u]=min(low[u],low[v]);
	}
	else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
	int v;cnt++;
	while(v!=u){
	    v=sta[top--],ins[v]=0;
	    sd[v]=cnt;
	    was[cnt]+=w[v];
	    val[cnt]+=a[v];
	}
    }
}
void treedp(int u){
    for(int i=was[u];i<=m;i++) dp[u][i]=val[u];
    for(int e=head[u];e;e=nxt[e]){
	int v=ver[e];
	treedp(v);
	for(int i=m-was[u];i>=0;--i)
	    for(int j=0;j<=i;++j)
		dp[u][i+was[u]]=max(dp[u][i+was[u]],dp[v][j]+dp[u][i+was[u]-j]);
    }
}
signed main(){
    n=read();m=read();
    for(int i=1;i<=n;++i) w[i]=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i){
	d[i]=read();
	if(d[i]) add1(d[i],i);
    }
    for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;++i){
	int x=sd[d[i]],y=sd[i];
	if(x!=y) add(x,y);
    }
    for(int i=1;i<=cnt;++i) if(!in[i]) add(0,i);
    treedp(0);
    cout<
图论——tarjanA——解题记录动态规划——树形DP

相关

标签