题解归档 - NC19981

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：NC19981
• 本地来源：problems/NC19981/idea.md
• 原始标题：NC19981 [HAOI2010] 软件安装

思路

NC19981 [HAOI2010] 软件安装

题意

• $n$ 个软件，容量 $m$；软件 $i$ 占 $w_i$、价值 $v_i$，依赖 $d_i$（$d_i=0$ 无依赖）。
• 只有依赖链上的软件都装了，$i$ 才计入价值。
• 求容量内最大总价值。

思路

• 依赖边 $i\to d_i$，每点出度 $\le1$ → 函数图，可能有环。
• Tarjan 缩点：环上软件必须整体选/不选，合并 $w,v$。
• 缩点后成森林，树上背包：$f[u][j]$ 为以 $u$ 为根的子树、必须选 $u$、容量 $j$ 的最大价值；儿子逐个合并。
• 多棵树的根再做一个背包合并进 dp[]。

强度

• 经典 HAOI2010 / 依赖背包 + 缩点，约 紫题 / 提高+ 水平。

代码

来源：problems/NC19981/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=110;
const ll maxm=510;
const ll inf=1e18;
vector<ll>ss[maxn+5],zczc[maxn+5],dqdq;
ll w[maxn+5],v[maxn+5],d[maxn+5],dfn[maxn+5],low[maxn+5],bel[maxn+5],sw[maxn+5],sv[maxn+5],p[maxn+5],f[maxn+5][maxm+5],dp[maxm+5];
bool ins[maxn+5];
ll timer,scc_cnt,m;
void tarjan(ll u){
    ll i,j,k,zc;
    dfn[u]=low[u]=++timer;
    dqdq.push_back(u);
    ins[u]=true;
    for(i=0;i<(ll)ss[u].size();i++){
        zc=ss[u][i];
        if(!dfn[zc]){
            tarjan(zc);
            low[u]=min(low[u],low[zc]);
        }else if(ins[zc]){
            low[u]=min(low[u],dfn[zc]);
        }
    }
    if(low[u]==dfn[u]){
        scc_cnt++;
        while(true){
            zc=dqdq.back();
            dqdq.pop_back();
            ins[zc]=false;
            bel[zc]=scc_cnt;
            sw[scc_cnt]+=w[zc];
            sv[scc_cnt]+=v[zc];
            if(u==zc) break;
        }
    }
}
void dfs(ll u){
    ll i,j,k,zc;
    for(j=0;j<=m;j++) f[u][j]=-inf;
    f[u][sw[u]]=sv[u];
    for(i=0;i<(ll)zczc[u].size();i++){
        zc=zczc[u][i];
        dfs(zc);
        for(j=m;j>=0;j--){
            for(k=0;k<=j;k++){
                if(f[zc][k]>-inf/2 and f[u][j-k]>-inf/2) f[u][j]=max(f[u][j],f[u][j-k]+f[zc][k]);
            }
        }
    }
}
int main(){
    ll n,i,j,k,zc,ans;
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=n;i++) scanf("%lld",&w[i]);
    for(i=1;i<=n;i++) scanf("%lld",&v[i]);
    for(i=1;i<=n;i++) scanf("%lld",&d[i]);
    for(i=1;i<=n;i++){
        if(d[i]) ss[i].push_back(d[i]);
    }
    for(i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    for(i=1;i<=scc_cnt;i++) p[i]=0;
    for(i=1;i<=n;i++){
        if(d[i] and bel[i]!=bel[d[i]]) p[bel[i]]=bel[d[i]];
    }
    for(i=1;i<=scc_cnt;i++){
        if(p[i]) zczc[p[i]].push_back(i);
    }
    for(i=1;i<=scc_cnt;i++){
        if(!p[i]){
            dfs(i);
            for(j=m;j>=0;j--){
                for(k=0;k<=j;k++){
                    if(f[i][k]>-inf/2) dp[j]=max(dp[j],dp[j-k]+f[i][k]);
                }
            }
        }
    }
    ans=0;
    for(i=0;i<=m;i++) ans=max(ans,dp[i]);
    printf("%lld\n",ans);
    return 0;
}