洛谷2515 [haoi2010]软件安装

tarjan重构图后树形DP

Posted by yjjr's blog on October 31, 2018

标签:Tarjan重构图,树形DP

题目

题目传送门

题目描述

现在我们的手头有个软件,对于一个软件i,它要占用的磁盘空间,它的价值为。我们希望从中选择一些软件安装到一台磁盘容量为计算机上,使得这些软件的价值尽可能大(即的和最大)。

但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件(包括软件j的直接或间接依赖)的情况下才能正确工作(软件依赖软件)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为

我们现在知道了软件之间的依赖关系:软件i依赖软件。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则,这时只要这个软件安装了,它就能正常工作。

输入输出格式

输入格式

第1行:

第2行:

第3行:

第4行:

输出格式

一个整数,代表最大价值

输入输出样例

输入样例#1

3 10
5 5 6
2 3 4
0 1 1

输出样例#1

5

分析

有先决条件的背包问题

考虑环的情况(要么选择整个环,要么整个舍弃)

首先用Tarjan把环的情况缩点重构图

然后跑一遍树形DP

设f[i][j]表示对i及其子树花费最多j的代价能够获得的最大价值

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
//**********head by yjjr**********
const int maxn=1e3+6;
int n,m,cnt,scc,tim=0,top=0,v[maxn],w[maxn],last[maxn],last2[maxn];
int sv[maxn],sw[maxn],dfn[maxn],low[maxn],bel[maxn],que[maxn],f[maxn][maxn],in[maxn];
struct edge{int to,next;}e[maxn],e2[maxn];
bool inque[maxn];
void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;}
void insert2(int u,int v){in[v]=1;e2[++cnt]=(edge){v,last2[u]};last2[u]=cnt;}
void tarjan(int x){
	int now=0;
	low[x]=dfn[x]=++tim;que[++top]=x;inque[x]=1;
	reg(x){
		int v=e[i].to;
		if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}
		else if(inque[v])low[x]=min(low[x],dfn[v]);
	}
	if(low[x]==dfn[x]){
		scc++;
		while(now!=x){
			now=que[top--];inque[now]=0;
			bel[now]=scc;
			sv[scc]+=v[now];
			sw[scc]+=w[now];
		}
	}
}
void rebuild(){
	cnt=0;
	rep(x,1,n)
		reg(x){
			int v=e[i].to;
			if(bel[v]!=bel[x])insert2(bel[x],bel[v]);
		}
}
void dp(int x){
#define reg2(x) for(int i=last2[x];i;i=e2[i].next) 
	reg2(x){
		int v=e2[i].to;
		dp(v);
		dep(j,m-sw[x],0)
			rep(k,0,j)f[x][j]=max(f[x][j],f[x][k]+f[v][j-k]);
	}
	dep(j,m,0){
		if(j>=sw[x])f[x][j]=f[x][j-sw[x]]+sv[x];
		else f[x][j]=0;
	}
}
int main()
{
	n=read(),m=read();
	rep(i,1,n)w[i]=read();
	rep(i,1,n)v[i]=read();
	rep(i,1,n){
		int x=read();
		if(x)insert(x,i);
	}
	rep(i,1,n)if(!dfn[i])tarjan(i);
	rebuild();
	rep(i,1,scc)
		if(!in[i])insert2(scc+1,i);
	dp(scc+1);
	cout<<f[scc+1][m]<<endl;
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr