HAOI 2010 软件安装（Tarjan+树形dp）

发表于 |
字数统计: 942字 | 阅读时长 ≈ 5min

【HAOI2010 Day1】软件安装

问题描述

现在我们的手头有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
第3行：V1,V2, … Vi, … ,Vn
第4行：D1,D2, … Di, … ,Dn

输出格式

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

样例输入

3 10
5 5 6
2 3 4
0 1 1

样例输出

5

此题看上去是裸的树形dp，然而，软件的依赖关系形成的是一个图，这个图可能有多个联通块，还可能存在环，因此需要用Tarjan缩点，然后添加一个虚拟的原点，向每一个缩点后的树根连边，构成一棵树，然后跑dp就好。

关于dp，将每个点看成一个$M-Wi$的背包，然后再把自己加进去就行了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#define N 1005
using namespace std;
int n,m,W[N],V[N],NW[N],NV[N],D[N];
int scc,VT,BE[N],low[N],dfn[N];
int TOT,LA[N],NE[N],ST[N],EN[N];
int tot,la[N],ne[N],en[N];
int F[N][N];
bool mark[N],map[N][N];
stack<int>S;
void ADD(int x,int y)
{
	TOT++;
	ST[TOT]=x;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void add(int x,int y)
{
	tot++;
	en[tot]=y;
	ne[tot]=la[x];
	la[x]=tot;
}
void Tarjan(int u)
{
	int i,v;
	dfn[u]=low[u]=++VT;
	S.push(u);mark[u]=1;
	for(i=LA[u];i;i=NE[i])
	{
		v=EN[i];
		if(!dfn[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(mark[v])low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		scc++;
		do{
			v=S.top();
			S.pop();
			mark[v]=0;
			BE[v]=scc;
			NW[scc]+=W[v];
			NV[scc]+=V[v];
		}while(u!=v);
	}
}
void DP(int x)
{
	int i,j,k,y;
	for(i=la[x];i;i=ne[i])
	{
		y=en[i];
		DP(y);
		for(j=m-NW[x];j>=0;j--)
		for(k=j;k>=0;k--)F[x][j]=max(F[x][j],F[x][k]+F[y][j-k]);
	}
	for(i=m;i>=0;i--)
	if(i>=NW[x])F[x][i]=F[x][i-NW[x]]+NV[x];
	else F[x][i]=0;
}
int main()
{
	int i,j,x,y,ans=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&W[i]);
	for(i=1;i<=n;i++)scanf("%d",&V[i]);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(x)ADD(x,i);
	}
	for(i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
	for(i=1;i<=TOT;i++)
	{
		x=ST[i];y=EN[i];
		if(BE[x]!=BE[y])add(BE[x],BE[y]),D[BE[y]]++;
	}
	BE[0]=scc+1;
	for(i=1;i<=scc;i++)if(!D[i])add(BE[0],i);
	DP(BE[0]);
	for(i=0;i<=m;i++)ans=max(ans,F[BE[0]][i]);
	printf("%d",ans);
}