题解 | 【模板】有依赖的背包问题

import java.io.*;
import java.util.*;

public class Main {
   // 存储并查集中节点 i 的父节点
    private static int[] parent;
    // 存储第 i 朵云（或合并后以 i 为根的商品组）的总价钱
    private static int[] cost;
    // 存储第 i 朵云（或合并后以 i 为根的商品组）的总价值
    private static int[] value;

    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 和 PrintWriter 提升大规模数据下的 I/O 效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 1. 读取基础配置：n 朵云, m 个搭配关系, w 现有的钱
        String[] strA = br.readLine().trim().split("\\s+");
        int n = Integer.parseInt(strA[0]);
        int m = Integer.parseInt(strA[1]);
        int w = Integer.parseInt(strA[2]);

        parent = new int[n + 1];
        cost = new int[n + 1];
        value = new int[n + 1];

        // 2. 初始化每朵云的属性，并初始化并查集（每个节点初始父节点为自己）
        for (int i = 1; i <= n; i++) {
            String[] strB = br.readLine().trim().split("\\s+");
            cost[i] = Integer.parseInt(strB[0]);
            value[i] = Integer.parseInt(strB[1]);
            parent[i] = i;
        }

        // 3. 处理搭配购买关系：使用并查集将必须一起买的云“联通”起来
        for (int i = 0; i < m; i++) {
            String[] strC = br.readLine().trim().split("\\s+");
            int u = Integer.parseInt(strC[0]);
            int v = Integer.parseInt(strC[1]);
            union(u, v);
        }

        // 4.将同一集合内所有云的价钱和价值全部累加到该集合的“根节点”上
        for (int i = 1; i <= n; i++) {
            int root = find(i);
            // 如果当前节点不是根节点，则将其属性转移给根节点
            if (root != i) {
                cost[root] += cost[i];
                value[root] += value[i];
                // 清空当前非根节点的属性，防止在后续背包计算中被重复统计
                cost[i] = 0;
                value[i] = 0;
            }
        }

        // 5. 执行 0/1 背包算法
        // dp[j] 表示在花费 j 元钱的情况下能获得的最大价值
        int[] dp = new int[w + 1];
        for (int i = 1; i <= n; i++) {
            // 只处理根节点（代表一个完整的“捆绑商品组”）
            if (parent[i] == i) {
                // 0/1 背包内层循环必须“逆序遍历”，防止同一商品被多次购买
                for (int j = w; j >= cost[i]; j--) {
                    // 状态转移方程：不买当前组 vs 买当前组（消耗钱，加价值）
                    dp[j] = Math.max(dp[j], dp[j - cost[i]] + value[i]);
                }
            }
        }

        // 6. 输出预算 w 内能获得的最大总价值
        out.println(dp[w]);

        // 刷新缓冲区并释放资源
        out.flush();
        out.close();
        br.close();
    }

    /**
     * 查找根节点（带路径压缩优化）
     */
    private static int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        // 将查找路径上的所有节点直接挂在根节点下，加速后续查找
        return parent[i] = find(parent[i]);
    }

    /**
     * 合并两个集合
     */
    private static void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // 将 I 树合并到 J 树下
            parent[rootI] = rootJ;
        }
    }

}