满分求调
查看原帖
满分求调
1269609
yiwugougou楼主2024/12/21 08:28
这个标题有点怪
#include<bits/stdc++.h>
using namespace std;
int n,m,wa;
int fa[10005],w[10005],c[10005],dp[10005];
int find(int x){
    if(x==fa[x]){
        return x;
    }else{
        fa[x]=find(fa[x]);
        return fa[x];
    }
}
void unionn(int i,int j){
    int i_fa=find(i);
    int j_fa=find(j);
    fa[i_fa]=j_fa;
    w[j_fa]+=w[i_fa];
    c[j_fa]+=c[i_fa];
}
int dpw[10005],dpc[10005];
int main(){
    cin>>n>>m>>wa;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i];
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        unionn(a,b);
    }
    int len=1;
    for(int i=1;i<=n;i++){
        if(fa[i]==i){
            dpw[len]=w[i];
            dpc[len]=c[i];
            len++;
        }
    }
    for(int i=1;i<=len;i++){
        for(int j=wa;j>=dpw[i];j--){
            dp[j]=max(dp[j],dp[j-dpw[i]]+dpc[i]);
        }
    }
    cout<<dp[wa];
    return 0;
}

WA on #11

2024/12/21 08:28
加载中...