洛谷P1455 搭配购买 题解 并查集+01背包

题目链接：https://www.luogu.com.cn/problem/P1455

解题思路：
这道题目就是首先用并查集把属于同一个集合的物品合到一起，然后对每一个集合的物品做01背包。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int f[maxn], c[maxn], d[maxn], n, m, V, dp[maxn];
// 01背包部分
void pack01(int c, int v) {
    for (int i = V; i >= c; i --)
        dp[i] = max(dp[i], dp[i-c]+v);
}
// 并查集部分
void init() {
    for (int i = 1; i <= n; i ++)
        f[i] = i;
}
int Find(int x) {
    if (x == f[x]) return x;
    return f[x] = Find(f[x]);
}
void Union(int x, int y) {
    int a = Find(x), b = Find(y);
    if (a == b) return;
    f[a] = f[b] = f[x] = f[y] = a;
    c[a] += c[b];
    d[a] += d[b];
}
int main() {
    cin >> n >> m >> V;
    init();
    for (int i = 1; i <= n; i ++) cin >> c[i] >> d[i];
    while (m --) {
        int u, v;
        cin >> u >> v;
        Union(u, v);
    }
    for (int i = 1; i <= n; i ++) if (Find(i)==i) pack01(c[i], d[i]);
    cout << dp[V] << endl;
    return 0;
}

洛谷P1455 搭配购买 题解 并查集+01背包

原文：https://www.cnblogs.com/quanjun/p/12337911.html