萌新求调
查看原帖
萌新求调
542879
_HCl_楼主2023/11/29 11:25

蒟蒻刚学OI,各位大佬路过帮忙看一下

#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[1001],v[1001];
int dfn[1001],low[1001],vis[1001],col[1001],num,tlog;
vector<int> e[1001],g[1001];
stack<int> s;
int sp[1001],val[1001],pre[1001];
void tarjan(int x){
	low[x]=dfn[x]=++tlog;
	s.push(x);
	vis[x]=1;
	for(int i=0;i<e[x].size();++i){
		int y=e[x][i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]); 
		}
		else if(vis[y])low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		num++;
		while(s.top()!=x){
			int u=s.top();
			s.pop();
			sp[num]+=w[u];
			val[num]+=v[u];
			col[u]=num;
			vis[u]=0;
		}
		s.pop();
		sp[num]+=w[x];
		val[num]+=v[x];
		col[x]=num;
		vis[x]=0;
	}
}
int dlog,DFN[1001],ID[1001],siz[1001],f[150][550],ind[1001];
void dfs(int x){
	DFN[x]=++dlog;
	ID[dlog]=x;
	siz[x]=1;
	for(int i=0;i<g[x].size();++i){
		int y=g[x][i];
		dfs(y);
		siz[x]+=siz[y];
		pre[DFN[y]]=pre[DFN[x]]+sp[x];
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i)scanf("%d",w+i);
	for(int i=1;i<=n;++i)scanf("%d",v+i);
	for(int i=1;i<=n;++i){
		int x;
		scanf("%d",&x);
		e[x].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<e[i].size();++j){
			int y=e[i][j];
			if(col[i]!=col[y])g[col[i]].push_back(col[y]),ind[col[y]]++;
		}
	} 
	for(int i=1;i<=num;++i){
		if(!ind[i])g[0].push_back(i);
	}
	dfs(0);
	for(int i=1;i<=dlog;++i){
		for(int j=pre[i];j<=m;++j){
			if(j+sp[ID[i]]<=m)f[i+1][j+sp[ID[i]]]=max(f[i+1][j+sp[ID[i]]],f[i][j]+val[ID[i]]);
			f[i+siz[ID[i]]][j]=max(f[i+siz[ID[i]]][j],f[i][j]);
		}
	}
	cout<<f[dlog+1][m];
}
2023/11/29 11:25
加载中...