题意
有$n$个软件可以安装,每个软件会占$w_i$的磁盘空间,价值为$v_i$ ,每个软件都有至多一个依赖。剩余磁盘空间为$m$,求安装软件的价值最大值
数据范围:$0 \le n \le 100,0 \le m \le 500,0 \le v_i \le 1000$
题解
因为可能存在环,即必须全部安装才能有贡献,所以用$\mathrm{Tarjan}$缩点
之后便是树形$\mathrm{dp}$,注意选择子节点必须选择父节点即可
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
const int N=100+10;
const int M=500+10;
int n,m;
int w[N],v[N],d[N];
int cnt,dep,tot;
int head[N],dfn[N],low[N],clr[N],sw[N],sv[N],deg[N],dp[N][M];
stack<int> S;
struct edge{
int nxt,to;
} e[M];
inline void add(int u,int v){
e[++cnt]=edge{head[u],v};
head[u]=cnt;
}
void Tarjan(int u){
dfn[u]=low[u]=++dep;
S.push(u);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!clr[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
tot++;
for(int t=0;t!=u;){
t=S.top();
S.pop();
clr[t]=tot;
sw[tot]+=w[t];
sv[tot]+=v[t];
}
}
}
void dfs(int u){
for(int i=sw[u];i<=m;i++)
dp[u][i]=sv[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
dfs(v);
for(int j=m;j>=sw[u];j--)
for(int k=j-sw[u];~k;k--)
dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(int i=1;i<=n;i++){
scanf("%d",&d[i]);
add(d[i],i);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
Tarjan(i);
cnt=0;
memset(head,0,sizeof(head));
for(int i=1;i<=n;i++)
if(clr[d[i]]!=clr[i]){
add(clr[d[i]],clr[i]);
deg[clr[i]]++;
}
for(int i=1;i<=tot;i++)
if(!deg[i])
add(0,i);
dfs(0);
printf("%d",dp[0][m]);
return 0;
}
版权属于:Pelom
本文链接:https://pelom.top/archives/88/
转载时须注明出处及本声明