【BZOJ-2427】软件安装 Tarjan + 树形01背包

2427: [HAOI2010]软件安装

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 960  Solved: 380
[Submit][Status][Discuss]

Description

现在我们的手头有N个软件，对于一个软件i，它要占用W_i的磁盘空间，它的价值为V_i。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即V_i的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件D_i。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则D_i=0，这时只要这个软件安装了，它就能正常工作。

Input

第1行：N, M  （0<=N<=100, 0<=M<=500）
      第2行：W₁, W₂, ... W_i, ..., W_n （0<=W_i<=M ）
      第3行：V₁, V₂, ..., V_i, ..., V_n  （0<=Vi<=1000 ）
      第4行：D₁, D₂, ..., D_i, ..., D_n （0<=D_i<=N, D_i≠i ）

Output

一个整数，代表最大价值。

Sample Input

3 10
5 5 6
2 3 4
0 1 1

Sample Output

5

HINT

Source

Day2

Solution

把环缩成一个点...

建立超级根0....

然后树形01背包

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 110

#define MAXM 510

struct EdgeNode{int next,to;}edge[MAXN<<],road[MAXN<<];

int head[MAXN],cnt=,first[MAXN],tot=;

inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}

inline void InsertEdge(int u,int v) {if (!u) return; AddEdge(u,v);}

int w[MAXN],v[MAXN],V[MAXN],W[MAXN],N,M;

int dfn[MAXN],low[MAXN],st[MAXN],top,visit[MAXN],belong[MAXN],size[MAXN],dfsn,scc;

inline void Tarjan(int x)

{

    dfn[x]=low[x]=++dfsn; visit[x]=; st[++top]=x;

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

        if (!dfn[edge[i].to]) Tarjan(edge[i].to),low[x]=min(low[x],low[edge[i].to]);

            else if (visit[edge[i].to]) low[x]=min(dfn[edge[i].to],low[x]);

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

        {

            int stp=;

            scc++;

            while (x!=stp) stp=st[top--],size[scc]++,W[scc]+=w[stp],V[scc]+=v[stp],belong[stp]=scc,visit[stp]=;

        }

}

inline void AddRoad(int u,int v) {tot++; road[tot].next=first[u]; first[u]=tot; road[tot].to=v;}

inline void InsertRoad(int u,int v) {AddRoad(u,v); AddRoad(v,u);}

bool flag[MAXN];

inline void Rebuild()

{

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

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

            if (belong[i]!=belong[edge[j].to])

                InsertRoad(belong[i],belong[edge[j].to]),flag[belong[edge[j].to]]=;

    for (int i=; i<=scc; i++) if (!flag[i]) InsertRoad(,i);

}

int f[MAXN][MAXM],g[MAXN][MAXM];

void DP(int x,int last)

{

    for (int i=first[x]; i; i=road[i].next)

        if (road[i].to!=last)

            {

                DP(road[i].to,x);

                for (int j=M-W[x]; j>=; j--)

                    for (int k=; k<j; k++)

                        g[x][j]=max(g[x][j],g[x][k]+f[road[i].to][j-k]);

            }

    for (int i=; i<=M-W[x]; i++) f[x][i+W[x]]=g[x][i]+V[x];

}

int main()

{

    N=read(),M=read();

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

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

    for (int f,i=; i<=N; i++) f=read(),InsertEdge(f,i);

    for (int i=; i<=N; i++) if (!dfn[i]) Tarjan(i);

    Rebuild();

    DP(,);

    printf("%d\n",f[][M]);

    return ;

}

【BZOJ-2427】软件安装 Tarjan + 树形01背包的相关教程结束。