洛谷 P2515 [HAOI2010]软件安装

链接:

P2515


题意:

给出 \(n\) 个点的重量,价值和它的依赖关系,再给出背包大小 \(m\),求最大价值。


分析:

这道题和选课有点像。但这题可能有多个点的依赖关系形成环,此时环内点的取舍关系是一致的,所以要先用 tarjan 缩点,强连通分量需要维护重量和以及价值和。缩点后构造一张由强连通分量形成的图,发现形成一个森林,自然想到让所有点与 \(0\) 节点相连变成一棵树。只连向入度为 0 的点以免重边。

在树上考虑一个类似背包的dp,设 \(f[u,j]\) 表示以 \(u\) 节点为树根,背包大小为 \(j\) 时的最大价值。由于有多个儿子,所以状态转移时考虑两重循环,第一层 \(j\) 从 \(m\) 到 \(w[u]\) 表示背包大小,第二层 \(k\) 从 \(j\) 到 \(w[u]\) 表示留给自己和之前儿子的背包大小,转移方程为:

\[f[u,j]=\max(f[u,j],f[u][k]+f[v][j-k]) \]

最后答案取 \(\max\{f[0,i]|0\leq i\leq m\}\)


代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=105;
const int M=505;
#define in read()
inline int read(){
	int p=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
	return p*f;
}
struct edge{
	int v,next;
}e[N];
int head[N],en;
inline void insert(int u,int v){
	e[++en].v=v;
	e[en].next=head[u];
	head[u]=en;
}
int n,m,w[N],val[N];
int low[N],dfn[N],sta[N],scc[N],sign,sum,top;
bool vis[N];
int sw[N],sv[N];
void tarjan(int u){
	dfn[u]=low[u]=++sign;
	vis[u]=true;sta[++top]=u;
	for(int i=head[u],v=e[i].v;i;i=e[i].next,v=e[i].v){
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		sum++;int i;
		do{
			i=sta[top--];
			vis[i]=false;
			scc[i]=sum;
			sw[sum]+=w[i];
			sv[sum]+=val[i];
		}while(i!=u);
	}
}

struct QWQ{
	int v,next;
}E[N<<1];
int h[N],fn;
void ins(int u,int v){
	E[++fn].v=v;
	E[fn].next=h[u];
	h[u]=fn;
}
bool p[N][N];
int f[N][M];
int gin[N],ans=0;
void bag(int u){
	for(int i=m;i>=sw[u];i--)
		f[u][i]=sv[u];
	for(int i=h[u];i;i=E[i].next){
		int v=E[i].v;
		bag(v);
		for(int j=m;j>=sw[u];j--){
			for(int k=j;k>=sw[u];k--)
				f[u][j]=max(f[u][j],f[u][k]+f[v][j-k]);			
		}
	}
//	cout<<u<<endl;
//	for(int i=0;i<=m;i++)
//		cout<<f[u][i]<<" ";
//	cout<<endl;
}
signed main(){
	n=in,m=in;
	for(int i=1;i<=n;i++)w[i]=in;
	for(int i=1;i<=n;i++)val[i]=in;
	for(int i=1;i<=n;i++)insert(in,i);
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int u=0;u<=n;u++)
		for(int j=head[u],v=e[j].v;j;j=e[j].next,v=e[j].v){
			if(scc[u]==scc[v]||p[scc[u]][scc[v]])continue;
			p[scc[u]][scc[v]]=true,ins(scc[u],scc[v]),gin[scc[v]]++;
		}
	for(int i=1;i<=sum;i++)
		if(!gin[i])ins(0,i);
	bag(0);
	for(int i=0;i<=m;i++)
		ans=max(ans,f[0][i]);
	cout<<ans;
	return 0;
}

题外话:

树形dp调死我了,,,

上一篇:噬神者2 狂怒解放 GE2RB SW


下一篇:Flink 从0到1学习 —— 如何使用 Side Output 来分流?