1252搭配购买

原题链接

这道题目就是把01背包和并查集结合到一起而已，我们可以把一个集合内部的所有元素的信息统一到祖先节点上，再对所有的集合做01背包，把每个集合看成一个物品，然后物品价值是集合内所有物品价值和，物品体积是集合内所有物品体积和。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;
int n, k, m, v[N], w[N], f[N], p[N];

int find(int x) 
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d%d", &n, &k, &m);
    
    for (int i = 1; i <= n; i ++ ) 
        scanf("%d%d", &v[i], &w[i]), p[i] = i;
    
    while (k -- ) 
    {
        int u, v;
        scanf("%d%d", &u, &v);
        p[find(u)] = find(v);
    }
    
    for (int i = 1; i <= n; i ++ ) 
    {
        if (p[i] == i) continue ;
        v[find(i)] += v[i], w[find(i)] += w[i];
    }
    
    for (int i = 1; i <= n; i ++ ) 
    {
        if (p[i] != i) continue ;
        for (int j = m; j >= v[i]; j -- ) 
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
    printf("%d\n", f[m]);
    
    return 0;
}