萌新10分求助
  • 板块P1455 搭配购买
  • 楼主luqyou
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/7/27 09:33
  • 上次更新2023/10/27 18:13:10
查看原帖
萌新10分求助
464732
luqyou楼主2022/7/27 09:33
#include<bits/stdc++.h>
using namespace std;
int f[1000001],v[1000001],m[1000001],k,x,y,z,a[1000001],b[1000001],c[1000001],dp[1000001];
void push(int x){
	k++;
	b[k]=x;
} 
int find(int x){
	if(f[x]!=x) f[x]=find(f[x]);
	return f[x];
}
void init(){
	for(int i=1;i<=x;i++){
		fa[i]=i;	
	}
}
int main(){
	scanf("%d%d%d",&x,&y,&z);
	for(int i=1;i<=x;i++){
		scanf("%d%d",&m[i],&v[i]);
	}
	for(int i=1;i<=y;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		if(find(u)!=find(v)) f[find(u)]=find(v);
	}
	for(int i=1;i<=x;i++){
		bool fl=0;
		for(int j=1;j<=k;j++){
			if(find(i)==b[j]){
				fl=1;
				a[j]+=v[i];
				c[j]+=m[i];
				break;
			}
		}
		if(!fl){
			push(find(i));
			a[k]+=v[i];
			c[k]+=m[i];
		}
	}
	for(int i=1;i<=k;i++){
		for(int j=z;j>=c[i];j--){
			dp[j]=max(dp[j],dp[j-c[i]]+a[i]);
		}
	}
	printf("%d",dp[z]); 
	return 0;
 } 
2022/7/27 09:33
加载中...