<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

Joe觉得云朵很美，决定去山上的商店买一些云朵。

商店里有 $n$ 朵云，云朵被编号为 $1,2,…,n$，并且每朵云都有一个价值。

但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限，所以他希望买的价值越多越好。

输入格式

第 $1$ 行包含三个整数 $n，m，w$，表示有 $n$ 朵云，$m$ 个搭配，Joe有 $w$ 的钱。

第 $2 \\sim n+1$行，每行两个整数 $c_i，d_i$ 表示 $i$ 朵云的价钱和价值。

第 $n+2 \\sim n+1+m$ 行，每行两个整数 $u_i，v_i$，表示买 $u_i$ 就必须买 $v_i$，同理，如果买 $v_i$ 就必须买 $u_i$。

输出格式

一行，表示可以获得的最大价值。

数据范围

$1 \\le n \\le 10000$,
$0 \\le m \\le 5000$,
$1 \\le w \\le 10000$,
$1 \\le c_i \\le 5000$,
$1 \\le d_i \\le 100$,
$1 \\le u_i,v_i \\le n$

输入样例：

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

输出样例：

1

思路

这道题就是普朴素的$0/1$背包，只要把一棵树内的所有物品看作一个就好了。

代码

#include <iostream>
using namespace std;
const int N = 10010;
int n,k,m;
int p[N];
int w[N],v[N];
int dp[N];
int find (int x) {
    if (p[x] != x) p[x] = find (p[x]);
    return p[x];
}
int main () {
    cin >> n >> k >> m;
    for (int i = 1;i <= n;i++) {
        p[i] = i;
        cin >> w[i] >> v[i];
    }
    while (k--) {
        int a,b;
        cin >> a >> b;
        a = find (a),b = find (b);
        if (a != b) p[a] = b;
    }
    for (int i = 1;i <= n;i++) {
        if (p[i] == i) continue;
        int x = find (i);
        w[x] += w[i];
        v[x] += v[i];
    }
    for (int i = 1;i <= n;i++) {
        if (p[i] != i) continue;
        for (int j = m;j >= w[i];j--) {
            dp[j] = max (dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout << dp[m] << endl;
    return 0;
}