[BZOJ2427] [HAOI2010]软件安装

题目描述

Description

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

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

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

Input

第1行:N, M  (0<=N<=100, 0<=M<=500)
第2行:W1, W2, … Wi, …, Wn (0<=Wi<=M )
第3行:V1, V2, …, Vi, …, Vn  (0<=Vi<=1000 )
第4行:D1, D2, …, Di, …, Dn (0<=Di<=N, Di≠i )

Output

一个整数,代表最大价值

Sample Input

3 10
5 5 6
2 3 4
0 1 1

Sample Output

5

题目分析:

给出了一个有树和环的树 因为如果有环肯定是整个环都选对答案才能有贡献 那么我们将环用tarjan缩点 用一个虚点将所有入度为0的点连接,然后跑一遍树上背包

树上背包不会QAQ 只好看了hzwer的题解 呐 不多说了 刷树形DP去!

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int deep[200],low[200],belong[200];
bool vis[200];
int dis[200];
int heada[200];
int headb[200];
int ww[200],vv[200];
int w[200],v[200];
int in[200];
int tot_a,tot_b,color,time;
struct your
{
    int to,next;
}a[1010],b[1010];
void add_a(int x,int y)
{
    a[++tot_a].next=heada[x];
    a[tot_a].to=y;
    heada[x]=tot_a;
}
void add_b(int x,int y)
{
    b[++tot_b].next=headb[x];
    b[tot_b].to=y;
    headb[x]=tot_b;
}
void tarjan(int x)
{
    deep[x]=low[x]=++time;
    dis[++dis[0]]=x;
    vis[x]=true;
    for(int i=heada[x];i;i=a[i].next)
    {
        if(!deep[a[i].to])
        {
            tarjan(a[i].to);
            low[x]=min(low[x],low[a[i].to]);
        }
        else if(vis[a[i].to])
            low[x]=min(low[x],deep[a[i].to]);
    }
    if(deep[x]==low[x])
    {
        int tmp;
        color++;
        do
        {
            tmp=dis[dis[0]--];
            belong[tmp]=color;
            vis[tmp]=false;
            vv[color]+=v[tmp];
            ww[color]+=w[tmp];
        }while(tmp!=x);
    }
}
int f[105][505];
void dfs(int x,int temp)
{
    for(int i=headb[x];i;i=b[i].next)
    {
        if(b[i].to==temp) continue;
        dfs(b[i].to,x);
        for(int j=m-ww[x];j>=0;j--)
            for(int k=0;k<=j;k++)
                f[x][j]=max(f[x][j],f[b[i].to][j-k]+f[x][k]);
    }
    for(int i=m;i>=0;i--)
        if(i>=ww[x]) f[x][i]=f[x][i-ww[x]]+vv[x];
        else f[x][i]=0;
}
int main()
{
    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;i<=n;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        if(tmp) add_a(tmp,i);
    }
    for(int i=1;i<=n;i++)
        if(!deep[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=heada[i];j;j=a[j].next)
            if(belong[i]!=belong[a[j].to])
                add_b(belong[i],belong[a[j].to]),in[belong[a[j].to]]++;
    for(int i=1;i<=color;i++)
        if(!in[i]) add_b(color+1,i);
    dfs(color+1,0);
    printf("%d",f[color+1][m]);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注