20pts,WA求条
查看原帖
20pts,WA求条
752094
MornHus楼主2023/10/26 21:47
#include<bits/stdc++.h>
using namespace std;
#define maxn 105

int read(){
	int x=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}

int n,m;
int w[maxn];
int v[maxn];
int W[maxn];
int V[maxn];


int dfn[maxn];
int color[maxn];
stack<int>s;
int vis[maxn];
int low[maxn];
int deep,sum;


int ind[maxn];
vector<int>g[maxn];
vector<int>g1[maxn];

int dp[maxn][505];

void tarjan(int now){
	dfn[now]=low[now]=++deep;
	s.push(now);
	vis[now]=1;
	
	for(int i=g[now].size()-1;i>=0;i--){
		int to=g[now][i];
		if(!dfn[to]){
			tarjan(to);
			low[now]=min(low[now],low[to]);
		}else if(vis[to]){
			low[now]=min(low[now],low[to]);
		}
	}
	
	if(dfn[now]==low[now]){
		sum++;
		while(1){
			int st=s.top();
			
			color[st]=sum;
			W[sum]+=w[st];
			V[sum]+=v[st];
			
			vis[st]=0;
			s.pop();
			if(st==now)break;
		}
	}
}
void dfs(int now){
	for(int i=W[now];i<=m;i++){
		dp[now][i]=V[now];
	}
	for(int i=g1[now].size()-1;i>=0;i--){
		int to=g1[now][i];
		dfs(to);
		for(int j=m-W[now];j>=0;j--){
			for(int k=0;k<=j;k++){
				dp[now][j+W[now]]=max(
				dp[now][j+W[now]]
				,
				dp[to][k]+dp[now][j+W[now]-1]
				
				);
			}
		}
	}
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=n;i++)w[i]=read();
	for(int i=1;i<=n;i++)v[i]=read();
	for(int i=1;i<=n;i++){
		int t=read();
		if(t)g[t].push_back(i);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i);
	}
//	for(int i=1;i<=n;i++)cout<<vis[i]<<endl;
	for(int i=1;i<=n;i++){
		for(int j=g[i].size()-1;j>=0;j--){
			int to=g[i][j];
			if(color[i]!=color[to]){
				ind[color[to]]++;
				g1[color[i]].push_back(color[to]);
			}
		}
	}
	for(int i=1;i<=sum;i++){
		if(!ind[i])g1[0].push_back(i);
	}
	dfs(0);
	cout<<dp[0][m];
	return 0;
}
2023/10/26 21:47
加载中...