2019浙工大迎新赛

2019浙工大迎新赛

Yukikaze的复仇

题意：

题解：

#include<bits/stdc++.h>
#include<time.h>
using namespace std;
const int maxn=2e6+5;
namespace DSU
{
    int  father[maxn],rank[maxn],candy[maxn];
    void init(int n){for(int i=1;i<=n;i++) {father[i]=i;rank[i]=1;}}
    int find(int x){return x==father[x]?x:father[x]=find(father[x]);}
    void unionSet(int x,int y)
    {
        int xx=find(x),yy=find(y);
        if(xx==yy) return;
        if(rank[xx]>rank[yy]) swap(xx,yy);
        father[xx]=yy;rank[yy]+=rank[xx];
        candy[yy]+=candy[xx];
    }
}
using namespace DSU;
int dp[maxn];
int main()
{
    int n,m,x,y,l,r,sum=0;
    scanf("%d%d%d%d",&n,&m,&x,&y);init(n);
    for(int i=1;i<=n;i++){
        scanf("%d",&candy[i]);sum+=candy[i];
    }
    while(m--){
        scanf("%d%d",&l,&r);
        unionSet(l,r);
    }
    vector<int>vc;
    for(int i=1;i<=n;i++){
        if(i==father[i]) vc.push_back(2*candy[i]);
    }
    sum+=x-y;
    if(sum<=0) {printf("-1");return 0;} 
    for(int i=0;i<vc.size();i++){
        for(int j=maxn-1;j>=vc[i];j--){
            dp[j]=max(dp[j],dp[j-vc[i]]+vc[i]);
        }
    }
    printf("%d",sum-dp[sum-1]);
}

2019浙工大迎新赛

原文：https://www.cnblogs.com/zx0710/p/14148991.html