[VIJOS 1250] 가장 용감 한 로봇.

배경
Wind 는 많은 로봇 을 설계 했다.하지만 그들 은 모두 자신 이 가장 강하 다 고 생각 하기 때문에 한 경기 가 시작 되 었 습 니 다 ~
묘사 하 다.
기계 사람들 은 누가 가장 용감 한 지 알 고 싶 어서 물건 을 옮 기 는 경 기 를 한다.
그들 은 창고 에 도착 했다. 그 안에 n 개의 물건 이 있 고 모든 물건 은 가치 가 있 는 Pi 와 무게 Wi 가 있 지만 어떤 물건 들 은 함께 놓 으 면 폭발 하고 폭발 은 전달 성 이 있다.(a 와 b 는 폭발 하고 b 와 c 는 폭발 하면 a 와 c 는 폭발 한다) 기계 사람들 은 이 로 인해 자신 이 어렵 게 Wind 에 게 서 사 기 를 친 장 비 를 손실 하고 싶 지 않다. 그래서 그들 은 능력 범위 내 에서 가장 많은 가치 있 는 물건 을 가 져 갈 수 있 는 지 알 고 싶 어 한다.자네 가 도와 줄 수 있 겠 나?
입력 형식
그룹 별 테스트 데이터
첫 번 째 행위 n, Wmax, k (0 < = n, Wmax, k < = 1000) 다음 n 행, 각 물품 의 Pi, Wi (0 < = Pi < = 1000, 1 < = wi < = 10, 모두 정수) 다음 k 행, 줄 당 2 개의 숫자 a, b 는 a 와 b 가 폭발 할 것 임 을 나타 낸다.
출력 형식
각 그룹의 데이터 출력 1 행위 에 대한 최대 가치
샘플 입력

3 10 1
100 1
200 5
10 5
1 2

샘플 출력

210

제한 하 다.
각 테스트 포인트 1s
문제 풀이: 집합 + 패 킷 을 찾 습 니 다.동시에 찾 을 수 없 는 물건 을 같은 그룹 에 넣 고 한 그룹 씩 나 누 어 최대 한 개의 물건 만 찾 을 수 있 는 가방 을 만 들 면 됩 니 다.for i = 1 - > 그룹 수 for j = maxV - > 0 for k = 1 - > 이 그룹 아 이 템 수
왜 이렇게 하면 각 조 가 최대 한 개의 물품 만 찾 을 수 있 습 니까?(g [i] 로봇 용량 이 i 일 때 가장 많이 얻 을 수 있 는 물품 가치 수 를 나타 낸다)
증명: 만약 에 두 개의 무게 가 각각 x, y 인 아 이 템 이 있다 면 x + y 를 업데이트 하려 면 g [x] 또는 g [y] 가 업데이트 되 었 을 것 임 을 설명 합 니 다. 그러나 이 때 는 매 거 용량 상한 선 이 거꾸로 매 거 진 것 이기 때문에 x + y 는 x 또는 y 보다 일찍 업데이트 되 기 때문에 각 조 에서 최대 하 나 를 가 져 옵 니 다.

#include
#include
#include
#include
#include
#define LiangJiaJun main
using namespace std;
int n,v,k,f[1004],g[1004];
int p[1004],w[1004];
int Find(int x){return (f[x]==x)?x:f[x]=Find(f[x]);}
int lop[1004][1004],cnt,sv[1004];
int LiangJiaJun(){
    scanf("%d%d%d",&n,&v,&k);
    for(int i=1;i<=n;i++)scanf("%d%d",&p[i],&w[i]);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=k;i++){
        int p,q,a,b;
        scanf("%d%d",&a,&b);
        p=Find(a);q=Find(b);
        if(p!=q)f[p]=q;
    }
    cnt=0;
    for(int i=1;i<=n;i++){
        bool lat=0;
        for(int j=1;j<=cnt;j++){
            if(lop[j][0]==Find(i)){
                lat=1;
                lop[j][++sv[j]]=i;
                break;
            }
        }
        if(lat)continue;
        lop[++cnt][0]=Find(i);
        lop[cnt][++sv[cnt]]=i;
    }
    for(int i=1;i<=cnt;i++){
        for(int j=v;j>=0;j--){
            for(int k=1;k<=sv[i];k++){
                if(j>=w[lop[i][k]])
                    g[j]=max(g[j],g[j-w[lop[i][k]]]+p[lop[i][k]]);
            }
        }
    }
    printf("%d
",g[v]);
    return 0;
}