Codeforces 741B Arpa's weak amphitheater and Mehrdad's valuable Hoses (并查集+分组背包)

题目大意：

就是有n个人，每个人都有一个体积和一个价值。这些人之间有有些人之间是朋友，所有具有朋友关系的人构成一组。现在要在这些组中至多选一个人或者这一组的人都选，在总容量为W的情况下，如何使得所选人的价值总和最大。

解题分析：

很明显有朋友关系的人需要用DFS或者并查集进行分组。考虑全选这一组的情况，需要将这一组的人打包，看成一个人，然后塞入对应的组中。之后的分组背包就能够实现全选这一组的人的情况。

#include <bits/stdc++.h>

using namespace std;

template<typename T>

inline void read(T&x){

    x=;int f=;char c=getchar();

    while(c<'' || c>''){ if(c=='-')f=-;c=getchar(); }

    while(c>='' && c<=''){ x=x*+c-'';c=getchar(); }

    x*=f;

}

const int N = 2e3+;

int n,m,w,fa[N],dp[N];

struct Node{ int val,col; Node(){ val=;col=; } }node[N];

vector<Node>vec[N];    

int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }

inline void merge(int u,int v){

    if(find(u)!=find(v))

        fa[find(v)]=find(u);

}

int main(){

    read(n);read(m);read(w);

    for(int i=;i<=n;i++)read(node[i].col),fa[i]=i;

    for(int i=;i<=n;i++)read(node[i].val);

    while(m--){

        int u,v;read(u);read(v);

        merge(u,v);

    }

    for(int i=;i<=n;i++){

        vec[find(i)].push_back(node[i]);   //对这些物品分组

    }

    for(int i=;i<=n;i++){

        if(find(i)!=i)continue;

        Node nowsum;

        for(int j=;j<vec[i].size();j++){

            nowsum.val+=vec[i][j].val;

            nowsum.col+=vec[i][j].col;

        }

        vec[i].push_back(nowsum);   //将整组的看成一个物品，后面分组背包的时候就能够直接考虑全选这一整组物品的情况

    }

    for(int k=;k<=n;k++){         //分组背包

        if(find(k)!=k)continue;

        for(int v=w;v>=;v--){

            for(int i=;i<vec[k].size();i++){

                Node now=vec[k][i];

                if(v-now.col<)continue;

                dp[v]=max(dp[v],dp[v-now.col]+now.val);

            }

        }

    }

    printf("%d\n",dp[w]);

}