[HAOI2010]软件安装（树形背包，tarjan缩点）

题目描述

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

输出格式：

一个整数，代表最大价值

思路：

望过去满眼的树形DP

和前面写的选课一模一样，只是cost需要输入

但很显然，你会这样

为什么呢？

后来想了半天，才发现

如果1依赖于2,2依赖于2,3依赖于1的化，这几个个点其实也能选，不过要选得一起选

所以，我们要用tarjan来缩点

把所有满足上图关系的点变为一个新点，并且与0连边即可

Q：环套树怎么办？

因为一个点只唯一依赖另一个点，所以入边一定为1

所以一定是环到树，不可能树到环，所以缩点没问题

懒了一下，用了stl

代码：

// luogu-judger-enable-o2
#include<iostream>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define rii register int i
#define rij register int j
#define rik register int k
using namespace std;
const int N=;const int M=;
struct E{
    int to,nxt;
}ed[N<<];
int H[N<<],cnt;
stack<int>sta;
bool ins[N];
int dp[N][M],v[N],w[N],d[N];
int tot,dfn[N],low[N];
int num,col[N],fv[N],fw[N];
int n,m,rd[N];
void add(int x,int y)
{
    cnt++;
    ed[cnt].to=y;
    ed[cnt].nxt=H[x];
    H[x]=cnt;
    return;
}
void read(int &in)
{
    int x=,f=;
    char ch;
    for(ch=getchar();(ch<''||ch>'')&&ch!='-';ch=getchar());
    if(ch=='-')
    {
        f=-;
        ch=getchar();
    }
    while(ch>=''&&ch<='')
    {
        x=(x<<)+(x<<)+ch-'';
        ch=getchar();
    }
    in=x*f;
    return;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++tot;
    ins[x]=true;sta.push(x);
    int t,k;
    for(rii=H[x];i;i=ed[i].nxt)
    {
        t=ed[i].to;
        if(!dfn[t])
        {
            tarjan(t);
            low[x]=min(low[x],low[t]);
        }
        else if(ins[t])
        {
            low[x]=min(low[x],dfn[t]);
        }
    }
    if(low[x]==dfn[x])
    {
        num++;
        do
        {
            k=sta.top();
            sta.pop();
            col[k]=num;
            fw[num]+=w[k];
            fv[num]+=v[k];
            ins[k]=false;
        }
        while(k!=x);
    }
    return;
}
void dfs(int x)
{
    for(rii=fw[x];i<=m;i++)
    {
        dp[x][i]=fv[x];
    }
    int t;
    for(rii=H[x];i;i=ed[i].nxt)
    {
        t=ed[i].to;
        dfs(t);
        for(rij=m-fw[x];j>=;j--)
        {
            for(rik=;k<=j;k++)
            {
                dp[x][j+fw[x]]=max(dp[x][j+fw[x]],dp[x][j+fw[x]-k]+dp[t][k]);
            }
        }
    }
    return;
}
int main()
{
//     freopen("software.in","r",stdin);
//     freopen("software.out","w",stdout);
    read(n);
    read(m);
    for(rii=;i<=n;i++)
    {
        read(w[i]);
    }
    for(rii=;i<=n;i++)
    {
        read(v[i]);
    }
    for(rii=;i<=n;i++)
    {
        read(d[i]);
        if(d[i])
        {
            add(d[i],i);
        }
    }
    for(rii=;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    memset(H,,sizeof(H));
    cnt=;
    for(rii=;i<=n;i++)
    {
        if(col[i]!=col[d[i]]&&d[i])
        {
        add(col[d[i]],col[i]);
        rd[col[i]]++;
        }
    }
    for(rii=;i<=num;i++)
    {
        if(!rd[i])
        {
            add(num+,i);
        }
        dfs(num+);
    }
    printf("%d\n",dp[num+][m]);
    return ;
}

 // luogu-judger-enable-o2
 #include<iostream>
 #include<stack>
 #include<cstdio>
 #include<cstring>
 #include<cstdlib>
 #define rii register int i
 #define rij register int j
 #define rik register int k
 using namespace std;
 const int N=;const int M=;
 struct E{
     int to,nxt;
 }ed[N<<];
 int H[N<<],cnt;
 stack<int>sta;
 bool ins[N];
 int dp[N][M],v[N],w[N],d[N];
 int tot,dfn[N],low[N];
 int num,col[N],fv[N],fw[N];
 int n,m,rd[N];
 void add(int x,int y)
 {
     cnt++;
     ed[cnt].to=y;
     ed[cnt].nxt=H[x];
     H[x]=cnt;
     return;
 }
 void read(int &in)
 {
     int x=,f=;
     char ch;
     for(ch=getchar();(ch<''||ch>'')&&ch!='-';ch=getchar());
     if(ch=='-')
     {
         f=-;
         ch=getchar();
     }
     while(ch>=''&&ch<='')
     {
         x=(x<<)+(x<<)+ch-'';
         ch=getchar();
     }
     in=x*f;
     return;
 }
 void tarjan(int x)
 {
     dfn[x]=low[x]=++tot;
     ins[x]=true;sta.push(x);
     int t,k;
     for(rii=H[x];i;i=ed[i].nxt)
     {
         t=ed[i].to;
         if(!dfn[t])
         {
             tarjan(t);
             low[x]=min(low[x],low[t]);
         }
         else if(ins[t])
         {
             low[x]=min(low[x],dfn[t]);
         }
     }
     if(low[x]==dfn[x])
     {
         num++;
         do
         {
             k=sta.top();
             sta.pop();
             col[k]=num;
             fw[num]+=w[k];
             fv[num]+=v[k];
             ins[k]=false;
         }
         while(k!=x);
     }
     return;
 }
 void dfs(int x)
 {
     for(rii=fw[x];i<=m;i++)
     {
         dp[x][i]=fv[x];
     }
     int t;
     for(rii=H[x];i;i=ed[i].nxt)
     {
         t=ed[i].to;
         dfs(t);
         for(rij=m-fw[x];j>=;j--)
         {
             for(rik=;k<=j;k++)
             {
                 dp[x][j+fw[x]]=max(dp[x][j+fw[x]],dp[x][j+fw[x]-k]+dp[t][k]);
             }
         }
     }
     return;
 }
 int main()
 {
 //     freopen("software.in","r",stdin);
 //     freopen("software.out","w",stdout);
     read(n);
     read(m);
     for(rii=;i<=n;i++)
     {
         read(w[i]);
     }
     for(rii=;i<=n;i++)
     {
         read(v[i]);
     }
     for(rii=;i<=n;i++)
     {
         read(d[i]);
         if(d[i])
         {
             add(d[i],i);
         }
     }
     for(rii=;i<=n;i++)
     {
         if(!dfn[i])
         {
             tarjan(i);
         }
     }
     memset(H,,sizeof(H));
     cnt=;
     for(rii=;i<=n;i++)
     {
         if(col[i]!=col[d[i]]&&d[i])
         {
         add(col[d[i]],col[i]);
         rd[col[i]]++;
         }
     }
     for(rii=;i<=num;i++)
     {
         if(!rd[i])
         {
             add(num+,i);
         }
         dfs(num+);
     }
     printf("%d\n",dp[num+][m]);
     return ;

题目描述

输入输出格式

思路：

代码：

个人收藏笔记记录

开通VIP