题目链接:https://codeforces.com/contest/741/problem/B
题目大意:有n个人,他们有的人可能是朋友关系。并且朋友关系可以传递。每个人两个属性w和v。
对于一个朋友团体,只能选择一个人,或者所有人,或者一个都没有,去参加舞会。要求w的和<W并且v的和最大。问v的和最大为多少。

思路:并查集维护团体,把w和v的和作为新成员。跑一个分组背包。

#include <bits/stdc++.h>
#define Rint register int
using namespace std;
 
int v[1005], w[1005], f[1005];
int d[1005][1005];
struct node{
    int w;
    int v;
};
 
vector<node> ve[1005];
 
int FD(int x){
    if(f[x]==-1){
        return x;
    }
    else{
        return f[x]=FD(f[x]);
    }
}
 
void LJ(int x, int y){
    x=FD(x), y=FD(y);
    if(x!=y){
        f[x]=y;
    }
}
 
int main(){
 
    memset(f, -1, sizeof(f));
    int n, m, s, a, b;
    scanf("%d%d%d", &n, &m, &s);
    for(int i=1; i<=n; i++){
        scanf("%d", &w[i]);
    }
    for(int i=1; i<=n; i++){
        scanf("%d", &v[i]);
    }
    for(int i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        LJ(a, b);
    }
    for(int i=1; i<=n; i++){
        ve[FD(i)].push_back(node{w[i], v[i]});
    }
    for(int i=1; i<=n; i++){
        int sw=0, sv=0;
        for(int j=0; j<ve[i].size(); j++){
            sw+=ve[i][j].w; sv+=ve[i][j].v;
            //cout<<i<<" : "<<ve[i][j].w<<" "<<ve[i][j].v<<endl;
        }
        ve[i].push_back(node{sw, sv});
        //cout<<i<<" ; "<<sw<<" "<<sv<<endl;
    }
    for(int i=1; i<=n; i++){
        for(int j=s; j>=0; j--){
            for(int k=0; k<ve[i].size(); k++){
                d[i][j]=max(d[i][j], d[i-1][j]);
                if(j>=ve[i][k].w){
                    d[i][j]=max(d[i][j], d[i-1][j-ve[i][k].w]+ve[i][k].v);
                }
            }
        }
    }
    printf("%d\n", d[n][s]);
 
    return 0;
}