BZOJ 2427: [HAOI2010]软件安装 树形背包

2427: [HAOI2010]软件安装

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1275  Solved: 492

[Submit][Status][Discuss]

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

5

首先说明 这个题有坑点 没有说是一棵树 得缩点 有可能是森林

昨天。。谁讲的来着。。。

反正学了树形背包 会了O(n*m*m)做法O(n*m)有待后续研究

缩点后增加根向所有无入度的点连边，树形背包 AC

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
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<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
const int N=110;const int M=550;
const int inf=0X7f7f7f7f;
int n,m,val[N],weight[N],dp[N][M],sccw[N],sccval[N];
int dfn[N],low[N],s[N],belong[N],size[N],top,cnt,scc;
int edcnt,head[N],last[N],ecnt,root[N];
bool indegree[N];
bool ins[N],vis[N];
struct EDGE{int to,nt;}ed[N<<2],e[N<<2];
inline void added(int u,int v){ed[++edcnt]=(EDGE){v,head[u]};head[u]=edcnt;}
inline void add(int u,int v){e[++ecnt]=(EDGE){v,last[u]};last[u]=ecnt;}
void tarjan(int u)
{
	dfn[u]=low[u]=++cnt;ins[u]=1;s[++top]=u;
	for(int i=head[u];i;i=ed[i].nt)
	{
		if(!dfn[ed[i].to])
		{tarjan(ed[i].to);low[u]=min(low[u],low[ed[i].to]);}
		else if(ins[ed[i].to]&&dfn[ed[i].to]<low[u])low[u]=dfn[ed[i].to];
	}
	if(dfn[u]==low[u])
	{
		scc++;int temp=0;
		do
		{
			temp=s[top--];ins[temp]=0;
			belong[temp]=scc;size[scc]++;
			sccw[scc]+=weight[temp];sccval[scc]+=val[temp];
		}
		while(temp!=u);
	}
}
void dfs(int u)
{
	for(int i=1;i<sccw[u];i++)dp[u][i]=0;
	for(int i=sccw[u];i<=m;i++)dp[u][i]=sccval[u];
	for(int i=last[u];i;i=e[i].nt)
	{
		if(vis[e[i].to])continue;vis[e[i].to]=1;
		dfs(e[i].to);
		for(int j=m;j>=sccw[u];j--)
		for(int k=1;k<=j-sccw[u];k++)
		dp[u][j]=max(dp[u][j],dp[e[i].to][k]+dp[u][j-k]);
	}
}
int main()
{
	n=read();m=read();int u;
	for(int i=1;i<=n;i++)weight[i]=read();
	for(int i=1;i<=n;i++)val[i]=read();
	for(int i=1;i<=n;i++){u=read();if(u)added(u,i);}
	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=ed[j].nt)
		{
			if(belong[i]!=belong[ed[j].to])
			{add(belong[i],belong[ed[j].to]);indegree[belong[ed[j].to]]=1;}
		}
	}
	for(int i=1;i<=scc;i++)if(!indegree[i])root[++root[0]]=i;
	for(int j=1;j<=root[0];j++)add(scc+1,root[j]);
	dfs(scc+1);
	printf("%d\n",dp[scc+1][m]);
	return 0;	
}
/*
3 10
5 5 6
2 3 4
0 1 1 

5
*/