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

点击量：132

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

目录

题目描述

现在我们的手头有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

   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;
}