bzoj 2427: [HAOI2010]软件安装

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

HINT

Source

Day2

由于是n个点n条边,所以是基环树森林,我们通过tarjan缩环后(环是捆绑选择的),就是森林

建立一个虚拟父亲后,就是一棵树了,然后就是经典的树型01背包问题了,但是zz选手竟然忘记树型背包了...

大致dp是这样的:f[i][j]表示i的子树花费j的体积产生的最大收益(如果选了i点就有值,不然就是0);

转移,对于以i为根的子树:

首先先不选i,然后和儿子的子树的收益进行合并:f[x][j]=max(f[x][j],f[x][k]+f[y][j-k]);

然后跟所有儿子搞完后,就来考虑选自身:

如果选不了自己的话,dp值为0,否则就直接加上(因为如果选不了i,那么i的子树中所有贡献都失效)

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<iostream>

#include<cstring>

#include<vector>

using namespace std;

typedef long long ll;

const int N=100050;

int gi()

{

    int x=0,flag=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();

    return x*flag;

}

int head[N],to[N],nxt[N],v[N],w[N],low[N],dfn[N],zhan[N],vis[N],cnt,tt,sum,tot,w2[N],v2[N],fr[N];

int n,m,f[1000][1000],ru[N];

vector<int>p[N];

void lnk(int x,int y){

    to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;

}

void tarjan(int x){

    low[x]=dfn[x]=++tt;vis[x]=1;zhan[++sum]=x;int y;

    for(int i=head[x];i;i=nxt[i]){

	y=to[i];

	if(!dfn[y]){

	    tarjan(y);

	    low[x]=min(low[y],low[x]);

	}

	else if(vis[y]) low[x]=min(low[x],dfn[y]);

    }

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

	tot++;

	do{

	    y=zhan[sum--];vis[y]=0;

	    w2[tot]+=w[y];v2[tot]+=v[y];fr[y]=tot;

	}while(y!=x);

    }

}

void dfs(int x){

    for(int i=0;i<p[x].size();i++){

	int y=p[x][i];dfs(y);

	for(int j=m-v2[x];j>=0;j--){

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

		f[x][j]=max(f[x][j],f[x][k]+f[y][j-k]);

	}

    }

    for(int i=m;i>=0;i--){

	if(i>=v2[x]) f[x][i]=f[x][i-v2[x]]+w2[x];

	else f[x][i]=0;

    }

}

int main(){

    n=gi();m=gi();int x;

    for(int i=1;i<=n;i++) v[i]=gi();

    for(int i=1;i<=n;i++) w[i]=gi();

    for(int i=1;i<=n;i++){

	x=gi();if(x!=0) lnk(i,x);

    }

    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);

    for(int i=1;i<=n;i++)

	for(int j=head[i];j;j=nxt[j]){

	    if(fr[i]!=fr[to[j]]) p[fr[to[j]]].push_back(fr[i]),ru[fr[i]]++;

	}

    int bigfa=tot+1;

    for(int i=1;i<=tot;i++) if(!ru[i]) p[bigfa].push_back(i);

    dfs(bigfa);printf("%d\n",f[bigfa][m]);

}

秒客网