P1455 搭配购买

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
    int parent;
    int price;  // 集合总价格
    int value;  // 集合总价值
};

vector<Node> nodes;

// 并查集查找，路径压缩
int find(int x) {
    if (nodes[x].parent != x) {
        nodes[x].parent = find(nodes[x].parent);
    }
    return nodes[x].parent;}

// 合并两个集合
void unite(int x, int y) {
    int fx = find(x);
    int fy = find(y);if (fx == fy) return;
    // 将fy的价格和价值合并到fx
    nodes[fx].price += nodes[fy].price;
    nodes[fx].value += nodes[fy].value;
    nodes[fy].parent = fx;}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    nodes.resize(n + 1);  // 商品编号1~n
    for (int i = 1; i <= n; ++i) {
        int p, v;
        cin >> p >> v;
        nodes[i].parent = i;
        nodes[i].price = p;
        nodes[i].value = v;}
    // 处理k个搭配
    for (int i = 0; i < k; ++i) {
        int a, b;
        cin >> a >> b;
        unite(a, b);}
    // 收集所有不重复的根节点（集合）
    vector<int> roots;
    vector<bool> is_root(n + 1, false);
    for (int i = 1; i <= n; ++i) {
        int root = find(i);
        if (!is_root[root]) {
            roots.push_back(root);
            is_root[root] = true;}}
    // 01背包动态规划
    vector<int> dp(m + 1, 0);
    for (int root : roots) {
        int cost = nodes[root].price;int val = nodes[root].value;
        for (int j = m; j >= cost; --j) {
            dp[j] = max(dp[j], dp[j - cost] + val);}}
    cout << dp[m] << endl;
    return 0;}

C129 并查集+01背包 P1455 搭配购买