洛谷 P2515 [HAOI2010]软件安装

题目描述

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

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

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

输入输出格式

输入格式：

第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 ）

输出格式：

一个整数，代表最大价值

输入输出样例

输入样例#1：

输出样例#1：

Tarjan缩点+树形dp

屠龙宝刀点击就送

#include <ctype.h>

#include <cstdio>

#define N 605

void read(int &x)

{

    x=;bool f=;

    char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') f=;ch=getchar();}

    while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

    x=f?(~x)+:x;

}

struct node

{

    int next,to;

}edge[N<<];

struct node2

{

    int next,to;

}edge2[N<<];

struct thing

{

    int v,w;

}th[N];

bool in[N],instack[N];

int head2[N],cnt2,f[N][N],w[N],v[N],stack[N],top,n,m,head[N],cnt,sumcol,col[N],dfn[N],low[N],tim;

void add(int u,int v)

{

    edge[++cnt].next=head[u];

    edge[cnt].to=v;

    head[u]=cnt;

}

int min(int a,int b){return a>b?b:a;}

int max(int a,int b){return a>b?a:b;}

void tarjan(int x)

{

    dfn[x]=low[x]=++tim;

    instack[x]=;

    stack[++top]=x;

    for(int i=head[x];i;i=edge[i].next)

    {

        int v=edge[i].to;

        if(instack[v]) low[x]=min(low[x],dfn[v]);

        if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);

    }

    if(low[x]==dfn[x])

    {

        int t;

        sumcol++;

        do

        {

            t=stack[top--];

            instack[t]=false;

            col[t]=sumcol;

            th[sumcol].v+=v[t];

            th[sumcol].w+=w[t];

        }while(t!=x);

    }

}

void dp(int x)//此处DP为树上01背包 

{

    for(int i=head2[x];i;i=edge2[i].next)

    {

        dp(edge2[i].to);//延伸的点继续dp

        for(int j=m-th[x].w;j>=;j--)

        {

            for(int k=;k<=j;k++) f[x][j]=max(f[x][j],f[x][k]+f[edge2[i].to][j-k]);

        }

    }

    for(int j=m;j>=;j--)

    {

        if(j>=th[x].w) f[x][j]=f[x][j-th[x].w]+th[x].v;

        else f[x][j]=;

    }

}

void add2(int u,int v)

{

    edge2[++cnt2].next=head2[u];

    edge2[cnt2].to=v;

    head2[u]=cnt2;

}

void rebuild()

{

    for(int i=;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].next)

        {

            int v=edge[j].to;

            if(col[v]!=col[i])

            {

                in[col[v]]=;

                add2(col[i],col[v]);

            }

        }

    }

}

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++) read(w[i]);

    for(int i=;i<=n;i++) read(v[i]);

    for(int x,i=;i<=n;i++)

    {

        read(x);

        if(x) add(x,i);

    }

    for(int i=;i<=n;i++) if(!dfn[i]) tarjan(i);

    rebuild();

    for(int i=;i<=sumcol;i++)

    {

        if(!in[i])

        {

            in[i]=;

            add2(sumcol+,i);

        }

    }

    dp(sumcol+);

    printf("%d",f[sumcol+][m]);

    return ;

}

巴特西

洛谷 P2515 [HAOI2010]软件安装

题目描述

输入输出格式

输入输出样例

最新文章

热门文章