题解 | 【模板】有依赖的背包问题

#include<bits/stdc++.h>
using namespace std;

const int N=1e4+10;

int n,m,money;
int c[N],d[N];
int w[N],v[N];
int fa[N];
int dp[N];

void pre(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	return;
}

int find(int x){
	if(x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}

void add(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx==fy){
		return;
	}else{
		w[fy]+=w[fx];v[fy]+=v[fx];
		w[fx]=0;v[fx]=0;
		fa[fx]=fy;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m>>money;
	
	pre();
	
	for(int i=1;i<=n;i++){
		cin>>c[i]>>d[i];
		w[i]=c[i];v[i]=d[i];
	}
	

	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	
	int res=0;
	for(int i=1;i<=n;i++){
		if(fa[i]==i){
			for(int j=money;j>=w[i];j--){
				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
				res=max(res,dp[j]);
			}
		}
	}
	
	cout<<res<<endl;
    return 0;
}