1 条题解

  • 0
    @ 2026-1-27 19:50:54
    #include <bits/stdc++.h>
    using namespace std;
    int n,m,w;
    struct stu{
    	int c,d;
    }crr[100100];
    
    int arr[200100];//arr-存放父亲结点
    int brr[200100];//brr-记录当前层数,用于优化
     
    struct stn{
    	int c,d;
    };
    struct stn drr[200100]={};
    
    int dp[200100]={};
    int find(int x){//寻找当前位置的父亲结点 
    	if(arr[x]==x)//如果当前的人指向自己 
    		return x; 
    	else
    		return find(arr[x]);//向上寻找父亲结点 
    }
    
    void unite(int a,int b){
    	a=find(a);//寻找a的父亲结点 
    	b=find(b);//寻找b的父亲结点
    	
    	if(a==b) return;//a和b是同一个父亲结点
    	//低层次向高层次合并 
    	if(brr[a] < brr[b]){
    		arr[a]=b;
    	}else if(brr[a] > brr[b]){
    		arr[b]=a;
    	}else{
    		arr[b]=a;
    		brr[a]++;//a的层数+a,把b合并到a 
    	}
    	 
    }
    int main() {
    	cin>>n>>m>>w;
    	
    	for(int i=1;i<=n;i++) cin>>crr[i].c>>crr[i].d;
    	
    	
    	//1.初始化
    	for(int i=1;i<=n;i++){
    		arr[i]=i;//每个人是自己的父亲结点 
    		brr[i]=1;//每个结点一开始只有一个人    
    	} 
    	
    	int a,b;
    	for(int i=1;i<=m;i++){
    		cin>>a>>b;
    		//把a能连接人与b能连接人想连接 
    		unite(a,b); 
    	} 
    	//把所有的数据都加到根节点去 
    	for(int i=1;i<=n;i++){
    		int a=find(i);//寻找根节点 
    		drr[a].c+=crr[i].c;
    		drr[a].d+=crr[i].d;
    	}
    	 
    	for(int i=1;i<=n;i++){
    		int a=find(i);//寻找根节点 
    		drr[i].c=drr[a].c;
    		drr[i].d=drr[a].d;
    	}
    	
    	dp[0]=0;
    	for(int i=1;i<=n;i++){
    		for(int j=w;j>=drr[i].c;j--){
    			dp[j]=max(dp[j],dp[j-drr[i].c]+drr[i].d);
    		}
    	} 
    	cout<<dp[w];
        return 0;
    }
    
    • 1

    信息

    ID
    1356
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者