题意

有$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/

转载时须注明出处及本声明