有一个数据过不了
查看原帖
有一个数据过不了
1033480
LiujunjiaNC楼主2024/7/11 22:30
#include<iostream>
using namespace std;
const int M = 1e4 + 10;
int father[M];
int c[M],d[M];
int dp[M];
int find(int x){
    if(x==father[x]) return father[x];
    return father[x] = find(father[x]);
}
void unionn(int a,int b){
    int x=find(a);
    int y=find(b);
    if(a!=b){
        father[y]=x;
        c[x] += c[y];
        d[x] += d[y];
    }
}
int main(){
	int n,m,w;
    scanf("%d %d %d",&n,&m,&w);
    for(int i=1;i<=n;i++) scanf("%d %d",&c[i],&d[i]);
    for(int i=1;i<=n;i++) father[i] = i;
    int u,v;
	for(int i=1;i<=m;i++){
        scanf("%d %d",&u,&v);
        unionn(u,v);
    }
  	for(int i=1;i<=n;i++){
        if(father[i]==i){
            for(int j=w;j>=c[i];j--){
                dp[j] = max(dp[j-c[i]]+d[i],dp[j]);
            }
        }
		
	}
	printf("%d",dp[w]);
    return 0;
}

2024/7/11 22:30
加载中...