AcWing算法提高课-4.1.2搭配购买

算法提高课整理

CSDN个人主页：更好的阅读体验

原题链接

题目描述

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

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

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

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

输入格式

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

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

第 $n+2～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 背包。

AC Code

$\text{C}++$

#include <iostream>
#pragma GCC optimize(2)

using namespace std;

const int N = 10010;

int n, m, k;
int f[N], p[N];
int v[N], w[N];

int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d%d", &n, &k, &m);
    for (int i = 1; i <= n; i ++ )
        scanf("%d%d", &v[i], &w[i]);
    
    for (int i = 1; i <= n; i ++ )
        p[i] = i; // 并查集初始化
    
    int a, b;
    while (k -- )
    {
        scanf("%d%d", &a, &b);
        a = find(a), b = find(b);
        if (a != b)
        {
            v[b] += v[a], w[b] += w[a];
            v[a] = 0, w[a] = 0;
            p[a] = b; // 对于两个有依赖的物品缩点，并累加体积和重量
        }
    }
    
    for (int i = 1; i <= n; i ++ ) // 0-1背包
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    printf("%d\n", f[m]);
    
    return 0;
}

---

最后，如果觉得对您有帮助的话，点个赞再走吧！