「HAOI2010」软件安装

发表于 | 分类于 | | 浏览量： 次

Tarjan种了树并背着包爬树？什么鬼qwq。

传送门

洛谷P2515

BZOJ2427

题解

对于这题，如果直接按照软件之间的依赖关系建图的话，将会建出来一棵基环树森林，并不好搞。

然后不难发现，对于一个环上的软件，要么全部安装，要么全部不装。

所以就可以愉快地缩点了。

缩完点之后，原图就变成了一片森林。

为了方便，可以再新建一个超级根，把所有根都连到超级根上。

然后树形DP，爬到树上背个包即可。

代码

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
#include<cstdio>
using namespace std;
const int maxn=105,maxm=505;
int n,m,top,idx,cnt,dfn[maxn],low[maxn],stack[maxn],id[maxn],F[maxn][maxm],deg[maxn];bool vis[maxn],C[maxn][maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct Graph
{
	int tot,lnk[maxn],son[maxn*2],nxt[maxn*2],w[maxn],v[maxn];
	inline void add_e(int x,int y){tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}G1,G2;
void Tarjan(int now,const Graph& G)
{
	dfn[now]=low[now]=++idx;
	vis[now]=true;stack[++top]=now;
	for(int i=G.lnk[now];i;i=G.nxt[i])
	{
		if(!dfn[G.son[i]])
		{
			Tarjan(G.son[i],G);
			if(low[G.son[i]]<low[now]) low[now]=low[G.son[i]];
		}
		else if(vis[G.son[i]]&&dfn[G.son[i]]<low[now]) low[now]=dfn[G.son[i]];
	}
	if(dfn[now]==low[now])
	{
		cnt++;
		do
		{
			id[stack[top]]=cnt;
			G2.w[cnt]+=G1.w[stack[top]];
			G2.v[cnt]+=G1.v[stack[top]];
			vis[stack[top]]=false;top--;
		}while(stack[top+1]!=now);
	}
}
void DFS(int now,const Graph& G)
{
	if(G.w[now]>m) return;
	for(int i=G.lnk[now];i;i=G.nxt[i])
	{
		DFS(G.son[i],G);
		for(int j=m-G.w[now];j;j--)
			for(int k=1;k<=j;k++)
				if(F[now][j-k]+F[G.son[i]][k]>F[now][j])
					F[now][j]=F[now][j-k]+F[G.son[i]][k];
	}
	for(int i=m;i>=G.w[now];i--) F[now][i]=F[now][i-G.w[now]]+G.v[now];
	for(int i=0;i<G.w[now];i++) F[now][i]=0;
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++) G1.w[i]=read();
	for(int i=1;i<=n;i++) G1.v[i]=read();
	for(int i=1;i<=n;i++)
	{
		int Di=read();
		if(Di) G1.add_e(Di,i);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i,G1);
	for(int i=1;i<=n;i++)
		for(int j=G1.lnk[i];j;j=G1.nxt[j])
			if(id[i]!=id[G1.son[j]]&&!C[id[i]][id[G1.son[j]]])
				{G2.add_e(id[i],id[G1.son[j]]);C[id[i]][id[G1.son[j]]]=true;deg[id[G1.son[j]]]++;}
	for(int i=1;i<=cnt;i++) if(deg[i]==0) G2.add_e(cnt+1,i);
	DFS(cnt+1,G2);
	printf("%d\n",F[cnt+1][m]);
	return 0;
}