tarjan+树上背包10分求助
查看原帖
tarjan+树上背包10分求助
520056
luoyx楼主2022/10/21 21:09
#include <bits/stdc++.h>
using namespace std;
int n,m;
int u,v;
const int N=1005;
int c[N],w[N];
vector<int> g[N];
int head[N],ecnt;
struct edge{
	int v,nxt;
}e[N];
void add(int u,int v){
	e[ecnt].v=v;
	e[ecnt].nxt=head[u];
	head[u]=ecnt++;
}
int dfn[N],ind,low[N],color[N],cnt;
bool flag[N];
stack<int> st;
void tarjan(int u){
	dfn[u]=low[u]=++ind;
	flag[u]=true;
	st.push(u);
	for(int i=0;i<g[u].size();i++){
		v=g[u][i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(flag[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		cnt++;
		int p;
		while(st.top()!=u){
			p=st.top();
			st.pop();
			color[p]=u;
			w[u]+=w[p];
			c[u]+=c[p];
			flag[p]=false;
		}
		st.pop();
		color[u]=u;
		flag[u]=false;
	}
}
int in[N];
int dp[N][N];
void dfs(int u){
	dp[u][c[u]]=w[u];
	if(head[u]==-1){
		return ;
	}
	for(int i=head[u];i+1;i=e[i].nxt){
		v=e[i].v;
		dfs(v);
		for(int j=m;j>=0;j--){
			for(int k=m;k>=j;k--){
				dp[u][k]=max(dp[u][k],dp[u][k-j]+dp[v][j]);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	for(int i=1;i<=n;i++){
		cin>>v;
		if(v==0) continue;
		g[v].push_back(i);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=n;i++){	
		for(int j=0;j<g[i].size();j++){
			v=g[i][j];
			if(color[i]!=color[v]){
				add(color[i],color[v]);
				in[color[v]]++;
				//cout<<i<<' '<<v<<endl;
			}               
		}
	}
	for(int i=1;i<=n;i++){
		if(color[i]==i&&in[i]==0){
			add(0,i);
		}
	}
	memset(dp,-0x3f,sizeof(dp));
	dfs(0);
	int ans=0;
	for(int i=0;i<=m;i++)
		ans=max(ans,dp[0][i]);
	cout<<ans;
}
2022/10/21 21:09
加载中...