洛谷 P2515 [HAOI2010]软件安装 题解【tarjan】【树上DP】【背包】

作者: wjyyy 分类: DP,tarjan,树形DP,背包,解题报告 发布时间: 2018-06-13 16:59

点击量:24

写到快要崩溃-树上背包细节真的很多,有太多值得注意的地方。

 

题目描述

现在我们的手头有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:
3 10
5 5 6
2 3 4
0 1 1
输出样例#1:
5
   首先可以看出,这是一个有依赖的背包,但是不能像金明的预算方案(NOIP2006)那样做。图中的依赖关系形成了一棵树一张图×细节1(解释:图中的依赖关系会成环)。然而软件发挥作用不能像拓扑排序那样依次查找。因为软件的依赖在没有安装时,该软件也是可以安装的,这样环上要想起作用是可以的,不过必须环上所有点都被安装。
 
   针对上面所提到的环,我们用tarjan缩点,缩点过程中要将环上所有点的空间、价值和依赖加成为一个点,这样环才能发挥作用。对于那些没有依赖的点或者环,按照题目输入,顺便将它依赖到0去。
 
   在树形DP过程中,我们需要注意的是:如果选这棵子树,那么子树的根是一定要选的,不然孩子选择再多也没有用。这样我们的DP数组就出来了:f[i][j]表示在以i为根的子树中,花费j大小的硬盘所能收获的最大价值是多少。我们在转移上来时,只要将磁盘花费加上根节点的花费,价值也加上根节点的价值。因此我们要控制枚举的范围,不能出现违法的转移(如x的某子树的根节点的磁盘消耗是12,而将f[x][10]从该子树的孩子处更新就是不合法的。
 
   还要注意,这个题由于入度为1,所以只会有简单环,在缩点的过程中是可以直接叠加的,但是如果出现复杂环,就需要在主函数里后置处理了。
 
   tarjan缩点是前几天多练的专题,可是这次还是打错了,明明in数组都开出来了,最后还是忘了判断。。。感觉自己真的很废啊。。。

 

Code:

#include<cstdio>
#include<cstring>
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
struct node
{
    int n;
    node *nxt;
    node (int n)
    {
        this->n=n;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[120],*tail[120];
int w[120],v[120],d[120],m;
int dfn[120],low[120],cnt=0;
bool in[120];//tarjan最易错的地方
int s[120],top=0;
int del[120];
void tarjan(int x)
{
    dfn[x]=++cnt;
    low[x]=dfn[x];
    node *p=&head[x];
    s[++top]=x;
    in[x]=true;
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(!dfn[p->n])
        {
            tarjan(p->n);
            low[x]=min(low[p->n],low[x]);
        }
        else
        {
            if(!in[p->n])
                continue;
            low[x]=min(low[x],dfn[p->n]);
        }
    }
    if(dfn[x]==low[x])
    {
        while(s[top]!=x)
        {
            w[x]+=w[s[top]];//叠加到一个点上去
            v[x]+=v[s[top]];//如果不是只有一个简单环,还要在主函数里处理
            del[s[top]]=x;
            in[s[top]]=false;
            top--;
        }
        in[s[top]]=false;
        top--;
    }
    return;
}
int dfind(int x)//如果处于多个环中,用并查集的处理方法,这个题貌似不需要,它只有简单环
{
    if(del[x]==x)
        return x;
    return del[x]=dfind(del[x]);
}
int f[120][520];//f[i][j] 表示在子树里花费j的磁盘所得到的最大价值(不含自己)
void dfs(int x)
{
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        p->n=del[p->n];
        dfs(p->n);
    }
    p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        for(int i=m;i>=w[p->n];i--)//转移后,i的内存有多大
            for(int j=0;j<=i-w[p->n];j++)//从p->n的子树中的多少转移过来,并防止越界
                f[x][i]=max(f[x][i],f[x][i-j-w[p->n]]+v[p->n]+f[p->n][j]);//要加上p->n自己
    }
    return;
}
int main()
{
    memset(f,0,sizeof(f));
    memset(dfn,0,sizeof(dfn));
    memset(in,0,sizeof(in));
    int n;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        del[i]=i;
        scanf("%d",&w[i]);
        tail[i]=&head[i];
    }
    tail[0]=&head[0];
    del[0]=0;
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&d[i]);
        tail[d[i]]->nxt=new node(i);
        tail[d[i]]=tail[d[i]]->nxt;
    }
    for(int i=0;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    //重新构图
    for(int i=0;i<=n;i++)
        tail[i]=&head[i];
    for(int i=1;i<=n;i++)
    {
        //这里代码写得有点麻烦,其实简单环不用并查集,这一段就是重新构图的过程
        del[i]=dfind(i);
        del[d[i]]=dfind(d[i]);
        if(del[i]==i)//判断是一个强连通分量的根
        {
            if(del[i]==del[d[i]])//如果这条边在同一个强连通分量上
            {
                tail[0]->nxt=new node(i);
                tail[0]=tail[0]->nxt;
            }
            else
            {
                tail[del[d[i]]]->nxt=new node(i);
                tail[del[d[i]]]=tail[del[d[i]]]->nxt;
            }
        }
    }
    dfs(0);
    printf("%d\n",f[0][m]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */