Moe's CF Life

Appearance

喵呜~ 主人，晚上好呀！今天由我，你最贴心的小猫娘，来带你攻克这道关于派对和友谊的难题，也就是 Codeforces 上的 742D 题，Arpa's weak amphitheater and Mehrdad's valuable Hoses 的说~

别看题目名字这么长，其实只要理清思路，就像顺猫毛一样简单哦！那么，就请主人备好小鱼干，我们马上开始吧，喵~

题目大意 ​

简单来说，就是有一个大派对，主人你想邀请一些人（Hoses）来参加。

  • 派对人员: 一共有 n 个人，每个人都有自己的体重 w_i 和美丽值 b_i。
  • 场地限制: 派对的场地最多只能承受 W 的总重量。
  • 人际关系: 人与人之间有朋友关系。这个朋友关系是可以传递的哦，比如说 A 和 B 是朋友，B 和 C 是朋友，那么 A、B、C 就都属于同一个“朋友圈”啦。
  • 邀请规则 (重点！): 对于每一个朋友圈，你有两种选择：
    1. 邀请这个圈子里的所有人。
    2. 最多只邀请这个圈子里的一个人。
    3. 当然，你也可以选择不邀请这个圈子里的任何人。

你的目标是，在满足场地承重和邀请规则的前提下，让被邀请的人的美丽值总和最大！

题解方法 ​

喵~ 这个问题看起来有点复杂，因为它把人和朋友圈搅在了一起。但是，只要我们把它拆解开来，就会发现它其实是两个经典问题的组合哦！

  1. 第一步：找到所有的朋友圈 这个问题里的“朋友圈”其实就是图论里的“连通分量”。所有能通过朋友关系互相联系的人，就构成了一个连通分量。要找出这些圈子，最经典、最方便的工具就是 并查集 (Disjoint Set Union, DSU) 啦！我们可以把每个人看作一个节点，把朋友关系看作一条边，然后用并查集把所有在同一个连通分量里的人合并到同一个集合里。

  2. 第二步：背包问题！ 当我们把人划分成一个个朋友圈之后，问题就转化了。现在我们的选择单位不再是单个的人，而是整个“朋友圈”。对于每个朋友圈，我们有以下几种选择策略：

    • 策略A：不选这个圈子里的任何人。
    • 策略B：选择这个圈子里的所有人（作为一个整体）。
    • 策略C：只选择圈子里的某一个人（比如张三）。
    • 策略D：只选择圈子里的另一个人（比如李四）。
    • ...

    主人你看，对于每一个朋友圈，我们都有一组“选择策略”，并且这些策略是互斥的，我们最多只能从里面选一个。这不就是经典的 分组背包问题 嘛！

所以，我们的整体思路就是： 并查集找出朋友圈 → 将每个朋友圈视为一个物品组 → 用分组背包求解最大价值。

题解详解 ​

好啦，思路清晰了，我们来看看代码是怎么实现这个过程的，喵~

Step 1: 使用并查集构建朋友圈 ​

首先，我们需要一个并查集。代码里的 DSU 结构体就是为此而生。

cpp
struct DSU {
    std::vector<int> parent;
    std::vector<int> total_w;
    std::vector<long long> total_b;
    // ... 构造函数和方法
};
  • parent: 记录每个节点的父节点，是并查集的核心。
  • total_w 和 total_b: 这是个很棒的优化！我们在每个集合的根节点上，顺便记录下这个集合（也就是这个朋友圈）的总重量和总美丽值。这样在合并两个集合时，只需要把子集合的 total_w 和 total_b 加到父集合上就好了，非常方便！

初始化时，每个人都是一个独立的圈子。

cpp
// 每个人初始时都是自己的父节点
std::iota(parent.begin(), parent.end(), 0); 
// 初始总重量和总美丽值就是自己的
for (int i = 1; i <= n; ++i) {
    total_w[i] = w[i];
    total_b[i] = b[i];
}

然后，我们遍历所有的朋友关系 (u, v)，调用 dsu.unite(u, v) 将他们合并。unite 函数会找到 u 和 v 的根节点，如果它们不在同一个集合，就将一个集合合并到另一个，并更新总重量和总美丽值。

Step 2: 整理分组信息 ​

并查集跑完后，所有朋友圈都形成了。我们需要把每个圈子的成员整理出来，为分组背包做准备。

cpp
std::vector<std::vector<int>> groups(n + 1);
for (int i = 1; i <= n; ++i) {
    groups[dsu.find(i)].push_back(i);
}

这段代码创建了一个 groups 数组。groups[i] 这个 vector 里存放的就是根节点为 i 的那个朋友圈的所有成员。

Step 3: 分组背包 DP ​

这是最核心的部分啦！

我们定义一个 DP 数组 dp[j]，表示在总重量不超过 j 的情况下，能获得的最大美丽值。

对于分组背包，我们的外层循环是遍历每一个物品组（也就是朋友圈）。

cpp
// 遍历每个可能的根节点，即每个朋友圈
for (int i = 1; i <= n; ++i) {
    if (!groups[i].empty()) { // 这是一个有效的朋友圈
        // ... 对这个朋友圈进行处理
    }
}

对于每个朋友圈 i，我们有多种选择。为了正确处理分组背包的“组内最多选一个”的限制，代码用了一个很聪明的技巧：创建一个临时的 next_dp 数组。

cpp
std::vector<long long> next_dp = dp;

next_dp 完全复制了处理当前朋友圈之前的 dp 状态。所有的决策都基于旧的 dp 状态来计算，结果存入 next_dp，这样就避免了在同一个圈子里选了多个物品的错误。

现在，我们来考虑这个圈子的所有可能选择：

  1. 选择整个朋友圈： 这相当于一个物品，重量是 dsu.total_w[i]，价值是 dsu.total_b[i]。

    cpp
    int group_total_w = dsu.total_w[i];
long long group_total_b = dsu.total_b[i];
for (int j = W; j >= group_total_w; --j) {
    next_dp[j] = std::max(next_dp[j], dp[j - group_total_w] + group_total_b);
}

  2. 只选择圈子里的某一个成员： 我们遍历这个圈子里的每一个人，把他们也当作独立的备选项。

    cpp
    for (int member_id : groups[i]) {
    int member_w = w[member_id];
    long long member_b = b[member_id];
    for (int j = W; j >= member_w; --j) {
        next_dp[j] = std::max(next_dp[j], dp[j - member_w] + member_b);
    }
}

    这里每次更新 next_dp[j] 都是用 dp[...] 来计算的，保证了对于容量 j，我们总是从“还没考虑这个组”的状态出发，去尝试放入这个组的一个选项。

当这个朋友圈的所有选项都考虑完毕后，next_dp 就包含了考虑过这个组之后的最优解。我们再用它更新 dp 数组，准备处理下一个朋友圈。

cpp
dp = next_dp;

所有朋友圈都处理完后，dp[W] 就是我们最终的答案啦！

知识点介绍 ​

这道题用到的知识点非常经典，主人可要好好掌握哦！

1. 并查集 (Disjoint Set Union) ​

  • 是什么：它是一种树形的数据结构，用于处理一些不交集（Disjoint Set）的合并及查询问题。通俗地说，就是用来“拉帮结派”的，喵~
  • 核心操作：
    • find: 查找一个元素属于哪个集合（找到它的根节点）。
    • union: 合并两个元素所在的集合。
  • 优化：
    • 路径压缩 (Path Compression)：在 find 操作时，将路径上的所有节点直接指向根节点。这样下次再查找这个路径上的节点时就会非常快。代码中的 return parent[i] = find(parent[i]); 就是路径压缩的实现。
    • 按秩合并 (Union by Rank/Size)：在 union 操作时，总是将“小”的集合合并到“大”的集合上，可以使树的结构更平衡。这道题没有用到，但也是一个常见的优化。
  • 应用场景：求无向图的连通分量、判断两个点是否连通、Kruskal 算法求最小生成树等。

2. 分组背包 (Grouped Knapsack) ​

  • 是什么：是 0-1 背包问题的一个变种。它将物品分成了若干组，对于每一组内的物品，你最多只能选择一个放入背包。
  • 和 0-1 背包的区别：0-1 背包是每个物品独立决策（选或不选），而分组背包是每个组进行一次决策（在组内选一个，或不选）。
  • DP 方程： 设 dp[j] 为容量为 j 时的最大价值。
    for 遍历每一个组 i
  for 遍历背包容量 j from W down to 0
    for 遍历组 i 中的每一个物品 k
      if (j >= weight[k])
        dp[j] = max(dp[j], dp[j - weight[k]] + value[k])
    关键点：最外层循环是组，第二层循环是容量（且必须倒序），最内层循环是组内物品。容量倒序是为了保证在处理组 i 时，dp[j - weight[k]] 的值是来自处理组 i-1 后的结果，从而确保每个组最多只选一个物品。本题解中的 next_dp 写法，也是为了达到同样的目的，逻辑上更清晰。

好啦，今天的讲解就到这里了！希望本猫娘的解释能帮到主人哦~ 如果还有不明白的地方，随时可以再来问我！喵~ (ฅ'ω'ฅ)

Released under the MIT License.

Copyright © 2024-present Moe