题目概述

有 $n$ 个软件和 $m$ 的容量，每个软件需要 $w_i$ 的容量，有 $v_i$ 的价值，同时依赖 $d_i$ 软件( $d_i=0$ 则没有依赖)。问最大的价值。

解题报告

这是道假题，软件可以认为是瞬间安装，所以互相依赖的多个软件可以同时安装。

那么也就是给出一张带环图，我们先把强连通分量缩点，然后就变成了森林，接下来刷树形分组背包就行了。

ps：我太naive了，以为树中不会出现强连通分量，然后就0sWA了10多次。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=100,maxm=500;

int n,m,w[maxn+5],v[maxn+5],D[maxn+5],g[maxn+5][maxm+5];
int E,lnk[2][maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];
int ti,dfn[maxn+5],low[maxn+5],top,stk[maxn+5],fa[maxn+5];
int sum[maxn+5],val[maxn+5],si[maxn+5];bool instk[maxn+5];
int tot;pair<int,int> e[maxn+5];

#define Add(ID,x,y) son[++E]=(y),nxt[E]=lnk[ID][x],lnk[ID][x]=E
void Tarjan(int x){
    dfn[x]=low[x]=++ti;stk[++top]=x;instk[x]=true;
    for (int j=lnk[0][x];j;j=nxt[j])
        if (!dfn[son[j]]) Tarjan(son[j]),low[x]=min(low[x],low[son[j]]);
        else if (instk[son[j]]) low[x]=min(low[x],dfn[son[j]]);
    if (dfn[x]==low[x])
        for (int y=stk[top--];;y=stk[top--])
            {fa[y]=x;sum[x]+=w[y];val[x]+=v[y];si[x]++;instk[y]=false;if (x==y) break;}
}
void DP(int x){
    if (sum[x]>m) return;
    for (int e=lnk[1][x];e;e=nxt[e]){
        DP(son[e]);
        for (int j=m-sum[x];~j;j--)
            for (int i=j;~i;i--)
                g[x][j]=max(g[x][j],g[x][j-i]+g[son[e]][i]);
    }
    for (int j=m;j>=sum[x];j--) g[x][j]=g[x][j-sum[x]]+val[x];for (int j=0;j<sum[x];j++) g[x][j]=0;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    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,x;i<=n;i++) {scanf("%d",&x);if (x) Add(0,x,i);}
    for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i);
    for (int i=1;i<=n;i++)
        for (int j=lnk[0][i];j;j=nxt[j])
            if (fa[i]!=fa[son[j]]) e[++tot]=mp(fa[i],fa[son[j]]);
    sort(e+1,e+1+tot);tot=unique(e+1,e+1+tot)-e-1;
    for (int i=1;i<=tot;i++) Add(1,e[i].fr,e[i].sc),D[e[i].sc]=1;
    for (int i=1;i<=n;i++) if (fa[i]==i&&!D[i]) Add(1,0,i);DP(0);
    return printf("%d\n",g[0][m]),0;
}