洛谷2515 [HAOI2010]软件安装

题意

有 $n(\le 100)$ 个软件可以安装，每个软件会占 $w_i$ 的磁盘空间，价值为 $v_i$ ，每个软件都有至多一个依赖。剩余磁盘空间为 $m(\le 500)$ ，问安装软件的价值最大值。

题解

环上的软件必须要全装才有收益，所以先缩点。然后把 $0$ 看成树根，并将它与无依赖的软件连边。

剩下的就是标准的树形背包问题，只是注意当前枚举的软件一定会安装，否则无法安装子树上的软件。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=105;
struct Edge {
    int next,to;
} edge[N];
stack <int> s;
int dfsord,scnt,id[N],low[N],scc[N],v2[N],w2[N];
int cnt,head[N],n,m,fa[N],v[N],w[N],in[N],f[N][505];

inline void init()
{
    cnt=0;
    memset(head,0,sizeof(head));
}

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void tarjan(int x)
{
    s.push(x);
    id[x]=low[x]=++dfsord;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (!id[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if (!scc[y]) low[x]=min(low[x],id[y]);
    }
    if (id[x]==low[x])
    {
        scnt++;
        while (!s.empty())
        {
            int t=s.top(); s.pop();
            scc[t]=scnt;
            v2[scnt]+=v[t];
            w2[scnt]+=w[t];
            if (t==x) break;
        }
    }
}

void dfs(int x)
{
    for (int i=w2[x];i<=m;i++) f[x][i]=v2[x];
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        dfs(y);
        for (int j=m;j>=w2[x];j--)
        {
            for (int k=j-w2[x];~k;k--)
            {
                f[x][j]=max(f[x][j],f[y][k]+f[x][j-k]);
            }
        }
    }
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) w[i]=read();
    for (int i=1;i<=n;i++) v[i]=read();
    for (int i=1;i<=n;i++) add(fa[i]=read(),i);
    for (int i=1;i<=n;i++) if (!id[i]) tarjan(i);
    init();
    for (int i=1;i<=n;i++)
    {
        if (scc[fa[i]]==scc[i]) continue;
        add(scc[fa[i]],scc[i]); //重新连边
        in[scc[i]]++;
    }
    for (int i=1;i<=scnt;i++) if (!in[i]) add(0,i);
    dfs(0);
    return !printf("%d",f[0][m]);
}