搭配购买

形式化题目

给定 $n$ 件物品，第 $i$ 件有价钱 $c_i$ 和价值 $d_i$ ；再给定 $m$ 条无向的"强制搭配"边 $(u,v)$ ：选中 $u$ 则必须选中 $v$ ，反之亦然。在总价钱不超过 $w$ 的前提下，求可选到的最大总价值。

正解

思路

先看搭配约束的本质：约束是双向且可传递的。买 $u$ 必买 $v$ ，买 $v$ 又必买与 $v$ 搭配的所有云……沿着搭配边一路传递下去，最终结论是：

买了连通块里的任何一朵云，就必须买下它所在连通块的全部云。

因此搭配关系把 $n$ 朵云划分成若干连通块，每个连通块只有两种状态：整块买（价钱 $C=\sum c_i$ ，价值 $D=\sum d_i$ ），或者整块不买。把每个连通块"缩"成一件物品，问题就变成：

若干件物品，每件最多选一次，预算 $w$ ，最大化总价值——标准 0/1 背包。

实现上用并查集维护连通块（路径压缩 + 按大小合并），再对每个根统计 $(C,D)$ ，最后跑一遍 0/1 背包： $dp[j]$ 表示花费不超过 $j$ 能获得的最大价值，每件物品倒序枚举 $j$ 从 $w$ 到 $C$ ，转移 $dp[j]=\max(dp[j],\ dp[j-C]+D)$ 。

以样例说明连通块的缩点结果（边 1–3、3–2、4–2 把 1,2,3,4 连成一块）：

graph LR
    subgraph 块A["块A：C=14, D=130（买不起）"]
        n1["云1: 3/10"]
        n2["云2: 3/10"]
        n3["云3: 3/10"]
        n4["云4: 5/100"]
    end
    subgraph 块B["块B：C=10, D=1"]
        n5["云5: 10/1"]
    end
    n1 --- n3
    n3 --- n2
    n4 --- n2

预算 $w=10$ ：块 A 总价 $14 > 10$ 买不起；块 B 恰好花 $10$ 得价值 $1$ ，答案为 $1$ 。

小规模演示背包转移（只保留块 B 一件物品， $C=10, D=1$ ）：

$j$	0~9	10
初始 $dp[j]$	0	0
更新后 $dp[j]$	0	$dp[0]+1=1$

可见每件物品只让 $j \geqslant C$ 的位置获得一次提升，倒序枚举保证了"只买一次"。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-06 10:00
# update_at: 2026-10-13 22:28

import sys


class DSU:
    """并查集 (Disjoint Set Union)"""

    def __init__(self, n: int):
        # 1-indexed, fa 初始指向自己，sz 初始为 1
        self.fa = list(range(n + 1))
        self.sz = [1] * (n + 1)

    def find(self, x: int) -> int:
        """查找根节点，两趟路径压缩：先走到根，再把整条路径挂到根上"""
        root = x
        while self.fa[root] != root:
            root = self.fa[root]
        while self.fa[x] != root:
            self.fa[x], x = root, self.fa[x]
        return root

    def same(self, x: int, y: int) -> bool:
        """判断 x 和 y 是否属于同一个集合"""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> bool:
        """按大小合并两个集合 (小树挂大树)；已在同一集合返回 False"""
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return False
        if self.sz[fx] < self.sz[fy]:
            fx, fy = fy, fx
        self.fa[fy] = fx
        self.sz[fx] += self.sz[fy]
        return True


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, w = next(data), next(data), next(data)

    cost = [0] * (n + 1)   # 每朵云的价钱，下标 1..n
    value = [0] * (n + 1)  # 每朵云的价值
    for i in range(1, n + 1):
        cost[i], value[i] = next(data), next(data)

    dsu = DSU(n)

    for _ in range(m):
        u, v = next(data), next(data)
        dsu.unite(u, v)  # 合并搭配关系：买 u 必买 v，反之亦然

    # 同一连通块捆绑成一件"套餐"：价钱与价值分别按根累加
    group_cost = [0] * (n + 1)
    group_value = [0] * (n + 1)
    for i in range(1, n + 1):
        root = dsu.find(i)
        group_cost[root] += cost[i]
        group_value[root] += value[i]

    # 分组背包（这里每组只有一个套餐，即普通 0/1 背包），dp[j] = 花不超过 j 能得的最大价值
    dp = [0] * (w + 1)
    for root in range(1, n + 1):
        c = group_cost[root]
        if c == 0 or c > w:  # 不是有货的根，或整组买不起，跳过
            continue
        d = group_value[root]
        for j in range(w, c - 1, -1):  # 倒序扫保证每件只买一次
            better = dp[j - c] + d > dp[j]
            if better:
                dp[j] = dp[j - c] + d

    print(dp[w])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 00:27
 * update_at: 2026-10-13 22:33
 */

// 搭配购买：并查集缩连通块 + 0/1 背包
// 买一朵云必须买搭配的云，且关系可传递，所以每个连通块要么整块买、要么不买。
// 把每个连通块看成一件 (总价钱, 总价值) 的物品，跑 0/1 背包即可。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int maxn = 10005;  // n <= 10000
const int maxw = 10005;  // w <= 10000

// 并查集竞赛精简版（不用 struct）：路径压缩 + 按大小合并
// 口诀：find 找根压到底，unite 小树挂大树
// 易错点：init 别只写 fa[i] = i，sz[i] 也要置 1；合并后 sz 只在新根上有效
// 和别的模板一起用时 maxn 只留一份

int fa[maxn], sz[maxn];  // sz[x] 仅在根上有效

void init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
}

// 查 x 的根，顺手把整条链压到根上
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

bool same(int x, int y) { return find(x) == find(y); }

// 小树挂大树，返回是否真的发生了合并
bool unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return false;
    if (sz[fx] < sz[fy]) swap(fx, fy);
    fa[fy] = fx;
    sz[fx] += sz[fy];
    return true;
}

int n, m, w;
ll cost[maxn];            // cost[i]：第 i 朵云的价钱
ll val[maxn];             // val[i]：第 i 朵云的价值

ll gc[maxn];              // gc[根]：该连通块的总价钱
ll gv[maxn];              // gv[根]：该连通块的总价值
ll dp[maxw];              // dp[j]：花费不超过 j 能获得的最大价值

int main() {
    scanf("%d %d %d", &n, &m, &w);
    for (int i = 1; i <= n; i++)
        scanf("%lld %lld", &cost[i], &val[i]);

    // 初始化并查集
    init(n);

    // 搭配关系逐条合并
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        unite(u, v);
    }

    // 每个连通块捆绑成一件物品：价钱、价值分别求和（下标用根编号）
    for (int i = 1; i <= n; i++) {
        int root = find(i);
        gc[root] += cost[i];
        gv[root] += val[i];
    }

    // 0/1 背包：每件物品（连通块）最多选一次，倒序枚举容量
    for (int i = 1; i <= n; i++) {
        if (find(i) != i) continue;   // 每个连通块只处理它的根一次
        ll c = gc[i];
        if (c > w) continue;          // 整块买不起，跳过
        ll d = gv[i];
        for (int j = w; j >= c; j--) {
            if (dp[j - c] + d > dp[j])
                dp[j] = dp[j - c] + d;
        }
    }

    printf("%lld\n", dp[w]);
    return 0;
}

复杂度

并查集（路径压缩 + 按大小合并）： $O((n+m)\,\alpha(n))$ ，近似线性。
背包：物品数不超过 $n$ ，状态 $w+1$ 个，共 $O(n \cdot w) \leqslant 10^8$ ，与 C++ 正解同阶（Python 实测约 2s，存在 TLE 风险）。
空间 $O(n+w)$ 。

总结

本题的题眼是识别"强制搭配 = 连通块整选"：双向约束沿边传递，闭包恰好是整个连通块。并查集负责缩点，0/1 背包负责选块，两个基础模型拼起来就是正解。瓶颈不在算法而在背包的 $O(nw)$ 常数，Python 实现需注意倒序枚举与跳过买不起的块。

目录

形式化题目

正解

思路

代码

复杂度

总结