【题目链接】 

 

【题目大意】

　　给出一张图，所有连通块构成分组，每个点有价值和代价，

　　要么选择整个连通块，要么只能在连通块中选择一个，或者不选，为最大价值

 

【题解】

　　首先我们用并查集求出连通块，然后对连通块进行分组背包即可。

 

【代码】

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define rep(i,n) for(int i=1;i<=n;i++)using namespace std;const int N=1010;int dp[N],f[N],n,m,x,y,size,w[N],b[N];vector
         
           v[N];int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);}int main(){      while(~scanf("%d%d%d",&n,&m,&size)){          rep(i,n)f[i]=i,v[i].clear();        rep(i,n)scanf("%d\n",&w[i]);          rep(i,n)scanf("%d\n",&b[i]);        rep(i,m){scanf("%d%d",&x,&y);f[sf(x)]=sf(y);}          rep(i,n)v[sf(i)].push_back(i);          memset(dp,0,sizeof(dp));          rep(i,n)if(sf(i)==i){              for(int j=size;j>=0;j--){                  int W=0,B=0;                  for(int k=0;k
          
           =w[v[i][k]])dp[j]=max(dp[j],dp[j-w[v[i][k]]]+b[v[i][k]]); }if(j>=W)dp[j]=max(dp[j],dp[j-W]+B); } }printf("%d\n",dp[size]); }return 0; }