10pts,只过第一个点/kk
查看原帖
10pts,只过第一个点/kk
252549
Iwara楼主2024/7/18 21:45

rt

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=305,MAXM=605;
struct edge{
	ll u,v,nxt;
}e[MAXN],dag[MAXN];
ll head[MAXN],edge_num;
void add_edge(ll From,ll To){
	edge_num++;
	e[edge_num]=(edge){From,To,head[From]};
	head[From]=edge_num;
	return;
}
ll head_dag[MAXN],edge_dag;
void add_dag(ll From,ll To){
	edge_dag++;
	dag[edge_dag]=(edge){From,To,head_dag[From]};
	head_dag[From]=edge_dag;
	return;
}
ll n,m;
ll w[MAXN],v[MAXN];
ll dp[MAXN][MAXM];
ll _w[MAXN],_v[MAXN];
ll fa[MAXN];
ll dfn[MAXN],low[MAXN],cnt,st[MAXN],top,scc[MAXN];
bool in_stack[MAXN];
void tarjan(ll now){
	dfn[now]=low[now]=++cnt;
	st[++top]=now;
	in_stack[now]=1;
	for(int i=head[now];i;i=e[i].nxt){
		if(!dfn[e[i].v]){
			tarjan(e[i].v);
			low[now]=min(low[now],low[e[i].v]);
		}
		else if(in_stack[e[i].v])low[now]=min(low[now],dfn[e[i].v]);
	}
	if(low[now]==dfn[now]){
		while(1){
			scc[st[top]]=now;
			_w[now]+=w[st[top]];
			_v[now]+=v[st[top]];
			in_stack[st[top]]=0;
			if(st[top]==now){
				top--;
				break;
			}
			top--;
		}
	}
	return;
}
ll dsu[MAXN];
ll Find(ll num){
	return dsu[num]==num?num:dsu[num]=Find(dsu[num]);
}
void solve(ll now){
//	cout<<"now "<<now<<endl; 
	for(int i=_w[now];i<=m;i++)dp[now][i]=_v[now];
	for(int i=head_dag[now];i;i=dag[i].nxt){
		solve(dag[i].v);
		ll l=m-_w[now];
		for(int j=m;j>=0;j--){
			for(int k=0;k<=j;k++){
				dp[now][j+_w[now]]=max(dp[now][j+_w[now]],dp[dag[i].v][k]+dp[now][j+_w[now]-k]);
			}
		}
	}
	return;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=n;i++)cin>>v[i];
	for(int i=1;i<=n;i++){
		cin>>fa[i];
		add_edge(fa[i],i);
	}
	for(int i=1;i<=n;i++)add_edge(0,i);
	tarjan(0);
	for(int i=1;i<=n;i++)dsu[i]=i;
	for(int i=1;i<=edge_num;i++){
		if(Find(scc[e[i].u])==Find(scc[e[i].v]))continue;
		add_dag(scc[e[i].u],scc[e[i].v]);
		dsu[Find(scc[e[i].u])]=Find(scc[e[i].v]);
	}
	solve(0);
	cout<<dp[0][m];
	return 0; 
} 
2024/7/18 21:45
加载中...