[HAOI2010] 软件安装

Author Avatar
空気浮遊 2018年04月24日
  • 在其它设备中阅读本文章

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;
}
    redbag
    redbag  2018-05-13, 13:26

    https://acxblog.site/archives/sol-luogu-2515.html

      ajcxsu
      ajcxsu  2018-05-14, 22:11

      (:зゝ∠) 捕获ylx