P2515 [HAOI2010] 软件安装

未全部联通（虚根未打完）的代码

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		w=w*10-'0'+ch;
		ch=getchar();
	}
	return w*f;
}
const int N=115;
vector <int> e[N],g[N];
int n,m,v[N],w[N],val[N],wei[N],sti[N],col[N],tot,dfn[N],low[N],sta[N],top,dp[N][N];
void Tarjan(int now){
	dfn[now]=low[now]=++tot;
	sti[now]=1;
	sta[++top]=now;
	int len = e[now].size();
	for(int i = 0 ; i<len ; i++){
		int to = e[now][i];
		if(!dfn[to]){
			Tarjan(to);
			low[now]=min(low[now],low[to]);
		}
		else{
			if(sti[to]){
				low[now]=min(low[now],low[to]);
			}
		}
	}
	if(low[now]==dfn[now]){
		int num=0;
		do{
			num=sta[top];
			col[num]=now;
			sti[num]=0;
			v[now]+=val[num];
			w[now]+=wei[num];
			--top;
		}while(now!=num&&top>0);
	}
}
void dfs(int now){
	for(int i = w[now] ; i<=m ; i++)
	dp[now][i]=v[now];
	int len = g[now].size();
	for(int i = 0 ; i<len ; i++){
		int to =g[now][i];
		dfs(to);
		for(int j = m ; j>=1 ; j--){
			for(int k = 1 ; k<=j ; k++){
				dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[to][k]);	
			}
		}
	}
	return ;
}
int main(){
	n=read(),m=read();
	for(int i = 1 ; i<=n ; i++){
		wei[i]=read();
	}
	for(int i = 1 ; i<=n ; i++){
		val[i]=read();
	}
	for(int i = 1 ; i<=n ; i++){
		int d=read();
		e[d].push_back(i);
	}
	Tarjan(0);
	for(int i = 0 ; i<=n ; i++){
		int len = e[i].size();
		for(int j = 0 ; j<len ; j++){
			int to = e[i][j];
			if(col[i]!=col[to]){
				g[i].push_back(to);
			}
		}
	}
	dfs(0);
	cout<<dp[0][m];
	return 0;
}

将图全部联通后

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		w=w*10-'0'+ch;
		ch=getchar();
	}
	return w*f;
}
const int N=115;
vector <int> e[N],g[N];
int n,m,v[N],w[N],val[N],wei[N],sti[N],col[N],tot,dfn[N],low[N],sta[N],top,dp[N][N];
bool vis[N];
void Tarjan(int now){
	dfn[now]=low[now]=++tot;
	sti[now]=1;
	sta[++top]=now;
	int len = e[now].size();
	for(int i = 0 ; i<len ; i++){
		int to = e[now][i];
		if(!dfn[to]){
			Tarjan(to);
			low[now]=min(low[now],low[to]);
		}
		else{
			if(sti[to]){
				low[now]=min(low[now],low[to]);
			}
		}
	}
	if(low[now]==dfn[now]){
		int num=0;
		do{
			num=sta[top];
			col[num]=now;
			sti[num]=0;
			v[now]+=val[num];
			w[now]+=wei[num];
			--top;
		}while(now!=num&&top>0);
	}
}
void dfs(int now){
	for(int i = w[now] ; i<=m ; i++)
	dp[now][i]=v[now];
	int len = g[now].size();
	for(int i = 0 ; i<len ; i++){
		int to =g[now][i];
		dfs(to);
		for(int j = m ; j>=1 ; j--){
			for(int k = 1 ; k<=j-w[now] ; k++){
				dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[to][k]);	
			}
		}
	}
	return ;
}
int main(){
	n=read(),m=read();
	for(int i = 1 ; i<=n ; i++){
		wei[i]=read();
	}
	for(int i = 1 ; i<=n ; i++){
		val[i]=read();
	}
	for(int i = 1 ; i<=n ; i++){
		int d=read();
		e[d].push_back(i);
	}
	for(int i = 1 ; i<=n ; i++)
	if(!dfn[i])
	Tarjan(i);
	for(int i = 0 ; i<=n ; i++){
		int len = e[i].size();
		for(int j = 0 ; j<len ; j++){
			int to = e[i][j];
			if(col[i]!=col[to]){
				g[col[i]].push_back(col[to]);
				vis[col[to]]=1;
			}
		}
	}
	for(int i = 1 ; i<=n ; i++){
		if(i==col[i]&&!vis[i]){
			g[0].push_back(i);
		}
	}
	dfs(0);
	cout<<dp[0][m];
	return 0;
}
/*
8 20
3 4 5 2 0 3 3 6
5 1 0 3 2 3 5 5
0 1 1 0 4 8 6 7*/

求各位大佬指点