[BZOJ2427]:[HAOI2010]软件安装（塔尖+DP）

题目传送门

题目描述

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

输入格式

第1行：N, M

第2行：${W}_{1}$,${W}_{2}$,...,${W}_{i}$,...,${W}_{n}$

第3行：${V}_{1}$,${V}_{2}$,...,${V}_{i}$,...,${V}_{n}$

第4行：${D}_{1}$,${D}_{2}$,...,${D}_{i}$,...,${D}_{n}$

输出格式

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

样例

样例输入：

3 10
5 5 6
2 3 4
0 1 1

样例输出：

数据范围与提示

0≤N≤100,0≤M≤500；0≤${W}_{i}$≤M；0≤${V}_{i}$≤1000；0≤${D}_{i}$≤N,${D}_{i}$≠i。

题解

看到这道题聪明的你应该会想到[NOIP2016]金明的预算方案。

可是这道题显然是那道题的升级版，一个软件在依赖别的软件的同时还有可能被另一个软件依赖，但是好消息是每一个软件只会依赖一个软件。

那么我们可以考虑树上DP。

首先，因为存在环，所以考虑塔尖的带权缩点，然后建立新图。

然后，将存好的这棵树进行先序遍历（DFS序），将遍历序存入队列que，并记录以i为跟节点的子树的大小coun。

所好了这些预处理之后，我们就可以愉快的进行DP啦～

先来定义DP，dp[i][j]表示从第i个软件到第n个软件，最多花费磁盘空间j所能获得的价值。

变成了01背包，对于每一个节点，会有两种情况：

　　1.安装它：占用磁盘空间，获得价值。

　　2.不安装：那么它的子树也不能安装。

那么写出状态转移方程：dp[i][j]=max(dp[i+1][j-w[que[i]]]+v[que[i]],dp[i+coun[que[i]]][j])。

时间复杂度：O(NM)。

模板题，一定要理解透彻！！！

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec

{

	int nxt;

	int to;

}e[101],wzc[101];//e为旧图，wzc为新图

int head[101],cnt,headw[101],cntw;

int w[101],v[101],d[101],new_w[101],new_v[101];//注意此处d为新图中点的出度，后面两个数组也用在新图

int que[101],coun[101];//如题解

int dp[501][501];

int dfn[101],low[101],sta[101],ins[101],c[101],num,top,tot;//塔尖用

void add(int x,int y)//旧图建边

{

	e[++cnt].nxt=head[x];

	e[cnt].to=y;

	head[x]=cnt;

}

void add_w(int x,int y)//新图建边

{

	wzc[++cntw].nxt=headw[x];

	wzc[cntw].to=y;

	headw[x]=cntw;

}

void tarjan(int x)//塔尖带权缩点

{

	dfn[x]=low[x]=++num;

	sta[++top]=x;

	ins[x]=1;

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

	{

		if(!dfn[e[i].to])

		{

			tarjan(e[i].to);

			low[x]=min(low[x],low[e[i].to]);

		}

		else if(ins[e[i].to])

			low[x]=min(low[x],dfn[e[i].to]);

	}

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

	{

		tot++;

		int y;

		do

		{

			y=sta[top--];

			ins[y]=0;

			c[y]=tot;

			new_w[tot]+=w[y];

			new_v[tot]+=v[y];

		}while(x!=y);

	}

}

void dfs(int x)//dfs预处理

{

	que[++que[0]]=x;

	coun[x]=1;

	for(int i=headw[x];i;i=wzc[i].nxt)

	{

		dfs(wzc[i].to);

		coun[x]+=coun[wzc[i].to];

	}

}

int main()

{

	int n,m;

	scanf("%d%d",&n,&m);

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

		scanf("%d",&w[i]);

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

		scanf("%d",&v[i]);

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

	{

		int y;

		scanf("%d",&y);

		if(y)add(y,i);

	}

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

		if(!dfn[i])tarjan(i);

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

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

			if(c[x]!=c[e[i].to])

			{

				add_w(c[x],c[e[i].to]);

				d[c[e[i].to]]++;

			}

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

		if(!d[i])add_w(0,i);//将森林连成树

	que[0]=-1;

	dfs(0);

	for(int i=tot;i;i--)

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

		{

			if(j>=new_w[que[i]])dp[i][j]=max(dp[i+1][j-new_w[que[i]]]+new_v[que[i]],dp[i+coun[que[i]]][j]);//dp

			else dp[i][j]=dp[i+coun[que[i]]][j];

		}

	cout<<dp[1][m]<<endl;

	return 0;

}

rp++

巴特西