首页 > 代码库 > 【BZOJ-2427】软件安装 Tarjan + 树形01背包

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

2427: [HAOI2010]软件安装

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

Description

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

Input

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

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=0,f=1; char ch=getchar();    while (ch<0 || ch>9) {if (ch==-) f=-1; ch=getchar();}    while (ch>=0 && ch<=9) {x=x*10+ch-0; ch=getchar();}    return x*f;}#define MAXN 110#define MAXM 510struct EdgeNode{int next,to;}edge[MAXN<<1],road[MAXN<<1];int head[MAXN],cnt=1,first[MAXN],tot=1;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]=1; 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=0;            scc++;            while (x!=stp) stp=st[top--],size[scc]++,W[scc]+=w[stp],V[scc]+=v[stp],belong[stp]=scc,visit[stp]=0;        }}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=1; 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]]=1;    for (int i=1; i<=scc; i++) if (!flag[i]) InsertRoad(0,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>=0; j--)                    for (int k=0; k<j; k++)                        g[x][j]=max(g[x][j],g[x][k]+f[road[i].to][j-k]);            }    for (int i=0; i<=M-W[x]; i++) f[x][i+W[x]]=g[x][i]+V[x];}int main(){    N=read(),M=read();    for (int i=1; i<=N; i++) w[i]=read();    for (int i=1; i<=N; i++) v[i]=read();    for (int f,i=1; i<=N; i++) f=read(),InsertEdge(f,i);    for (int i=1; i<=N; i++) if (!dfn[i]) Tarjan(i);    Rebuild();    DP(0,0);    printf("%d\n",f[0][M]);    return 0;}

 

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