最勇敢的机器人（分组背包）

题目描述

机器人们都想知道谁是最勇敢的，于是它们比赛搬运一些物品。

它们到了一个仓库，里面有n个物品，每个物品都有一个价值Pi和重量Wi，但是有些物品放在一起会爆炸，并且爆炸具有传递性。（a和b会爆炸、b和c会爆炸则a和c会爆炸）

机器人们可不想因此损失自己好不容易从Wind那里敲诈来的装备，于是它们想知道在能力范围内，它们最多可以拿多少价值的物品。

输入输出格式

输入格式：

第1行为n,Wmax,k(0<=n,Wmax,k<=1000)

接下来n行，为每个物品的Pi,Wi(0<=Pi<=1000,1<=Wi<=10,均为整数)。

再接下来k行，每行2个数字a,b表示a和b会发生爆炸。

输出格式：

对每组数据输出1行。

为最大可能价值。

输入输出样例

 

输入样例#1：

3 10 1
100 1
200 5
10 5
1 2

输出样例#1：

210

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
struct data{
    int p,w;
}a[2000];
int f[2000],b[2000],h[2000][2000];
int wmax,n,k,m;
int get(int x){
    if(f[x]==x) return x;
    f[x]=get(f[x]);
    return f[x];
}
int main(){
    scanf("%d %d %d",&n,&wmax,&k);
    for(int i=1;i<=n;i++) scanf("%d %d",&a[i].p,&a[i].w);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=k;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        f[get(x)]=get(y);
    }
    for(int i=1;i<=n;i++) h[get(i)][++h[get(i)][0]]=i;
    for(int i=1;i<=n;i++){
        if(h[i][0]==0) continue;
        for(int v=wmax;v>=0;v--)
         for(int j=1;j<=h[i][0];j++){
             int num=h[i][j];
             if(v-a[num].w>=0)
              if(b[v]<b[v-a[num].w]+a[num].p) b[v]=b[v-a[num].w]+a[num].p;
         }
    }
    printf("%d",b[wmax]);
    return 0;
}

详见背包九讲