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

2023-12-20 14:31:01

算法提高课整理

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

Start

原题链接
题目描述

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

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

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

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

输入格式

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

2 ~ n + 1 2 \sim n+1 2n+1行,每行两个整数 c i , d i c_i,d_i ci?,di? 表示 i i i 朵云的价钱和价值。

n + 2 ~ n + 1 + m n+2 \sim n+1+m n+2n+1+m 行,每行两个整数 u i , v i u_i,v_i ui?,vi?,表示买 u i u_i ui? 就必须买 v i v_i vi?,同理,如果买 v i v_i vi? 就必须买 u i u_i ui?

输出格式

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

数据范围

1 ≤ n ≤ 10000 1 \le n \le 10000 1n10000,
0 ≤ m ≤ 5000 0 \le m \le 5000 0m5000,
1 ≤ w ≤ 10000 1 \le w \le 10000 1w10000,
1 ≤ c i ≤ 5000 1 \le c_i \le 5000 1ci?5000,
1 ≤ d i ≤ 100 1 \le d_i \le 100 1di?100,
1 ≤ u i , v i ≤ n 1 \le u_i,v_i \le n 1ui?,vi?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

C + + \text{C}++ 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;
}

228aa7bed3e021faf24cf8560d3e47bb.gif

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

文章来源:https://blog.csdn.net/xingchen_2008/article/details/135105291
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。