Problem

现在我们的手头有 N 个软件，对于一个软件 i，它要占用 Wi 的磁盘空间，它的价值为 Vi。我们希望从中选择一些软件安装到一台磁盘容量为 M 计算机上，使得这些软件的价值尽可能大（即 Vi 的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件 i 只有在安装了软件 j（包括软件 j 的直接或间接依赖）的情况下才能正确工作（软件 i 依赖软件 j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为 0。

我们现在知道了软件之间的依赖关系：软件 i 依赖软件 Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则 Di=0，这时只要这个软件安装了，它就能正常工作。

Solution

WA 了很久的题，之前是用的 Tarjan 缩点，现在发现自己还是图样

将环缩点之后，跑一个树状 dp 就行

怎么缩点？因为肯定是一个环（每个点最多只能连一条边），跟求解最小树型图的中间过程有点像，隆重介绍朱刘算法的 n 边树形图判环方法

其实就是基础判环，但不可否认它很好用

具体请在博客内搜索最小树形图的博客～那个判环方法真的是相当好用。

当然你不知道最小树形图也是能做的。具体可以看代码呀

Code

// Code by ajcxsu
// Problem: installation

#include<bits/stdc++.h>
using namespace std;

const int N=200, M=1000;
set<int> to[N];
int l[N], r[N];

int w[N], val[N], W[N], V[N], c[N], d[N], cn;
int fa[N];

void dfs(int x) {
    for(set<int>::iterator it=to[x].begin(); it!=to[x].end(); it++) {
        r[*it]=l[x], l[x]=*it;
        dfs(*it);
    }
}

int f[N][501];
int n,m;
inline int dp(int i,int j) {
    if(i==-1) return 0;
    if(f[i][j]!=-1) return f[i][j];
    f[i][j]=0;
    if(j>=W[i]) {
        for(int k=0;k<=j-W[i];k++)
            f[i][j]=max(f[i][j], V[i]+dp(r[i], k)+dp(l[i], j-W[i]-k));
    }
    f[i][j]=max(f[i][j], dp(r[i], j));
    return f[i][j];
}

int main() {
    ios::sync_with_stdio(false);
    memset(f,-1,sizeof(f)), memset(l,-1,sizeof(l)), memset(r, -1, sizeof(r));
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=n;i++) cin>>val[i];
    for(int i=1;i<=n;i++) cin>>d[i];
    for(int i=1,v;i<=n;i++) {
        v=i;
        while(fa[v]!=i && !c[v] && v) {
            fa[v]=i;
            v=d[v];
        }
        if(!c[v] && v) {
            ++cn;
            while(!c[v]) c[v]=cn, W[cn]+=w[v], V[cn]+=val[v], v=d[v];
        }
    }
    for(int i=1;i<=n;i++) if(!c[i]) c[i]=++cn, W[cn]=w[i], V[cn]=val[i];
    for(int i=1;i<=n;i++) {
        if(c[d[i]]==c[i]) to[0].insert(c[i]);
        else to[c[d[i]]].insert(c[i]);
        assert(c[i]);
    }
    dfs(0);
    cout<<dp(0,m)<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2515.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆